letzte Aktualisierung
|
Sudoku - Info zur Online-Applikation |
|
Zweck Ein Sudoku ist eine Rätsel-Aufgabe, in der schon einige Felder
mit Ziffern vorbelegt sind. Mit dieser Online-Anwendung löst oder verifiziert man Sudokus. Man stellt damit aber auch sicher, dass es nur eine Lösung gibt. Der Durchlaufzähler ist ein neutrales Maß zur schnellen Beurteilung der Komplexität des Sudokus. Bedienung
Button "Try to solve" startet den Lösungs-Suchvorgang. Wenn ein Ergebnis angezeigt wird,
kann man mit Button "Back" zurück zur ursprünglichen Aufgabe. Mit dem Button darunter geht man in dem Fall weiter zur nächsten Aufgabe. Button "Reset" löscht alle Felder, ein möglicherweise laufender Suchvorgang wird beendet. Der Button "Load File" ermöglicht, lokal verfügbare Sudoku-Dateien zu laden. Mit lokal verfügbar ist der Rechner gemeint, von dem aus der Browser gestartet wurde. Diese Sudoku-Dateien sind reine Textdateien mit einer Zeile pro Sudoku. Gültiger Zeilenaufbau:
Beispiel: # Datei mit Namen Sud_bsp.txt >aaaaaaaaabbbbbbbbbcccccccccdddddddddeeeeeeeeefffffffffggggggggghhhhhhhhhiiiiiiiii< Format 9 * 9 >0 1 2 3 4 5 6 7 8 < > 21 85 15 2 43 3 1 8 5 6 3 1 4 9 6 72 3 59 34 27 < Zei 13.01.2022 > 3 4 875 6 2 6 9 1 7 7 1 2 5 3 8 < Sudoku17 99805 Zeilen ohne gültigen Zeilenaufbau werden ignoriert. In diesem Beispiel also die ersten drei Zeilen. Aufbau Die Anwendung ist ein JavaScript und läuft mit den gängigen Web-Browsern und auf verschiedenen Betriebssystemen. Sogar der inzwischen etwas betagte und manchmal eher etwas störrische Internet-Explorer lässt sich für eine korrekte Funktion des Scripts überreden. Auch auf Mobiltelefonen lassen sich mit dieser Web-Anwendung Sudokus lösen und verifizieren. Interner Ablauf Der Kern des Lösers besteht aus einer kompakten Such-Routine, die sich ausschließlich um ein einzelnes Feld kümmert. Sie ermittelt, welche Ziffern für dieses Feld in Frage kommen, trägt die erste davon versuchsweise ein und ruft die gleiche Routine reentrant für das nächste Feld auf. Wenn dies mit allen Feldern nacheinander gelungen ist, wenn also auch für das letzte Feld eine gültige Ziffer vorliegt, hat man automatisch eine Lösung. Der Weg dahin ist für die Such-Routine allerdings nicht einfach. In den weitaus meisten Fällen endet ein Suchpfad damit, dass sie bei einem Feld landet, für das es keine gültige Ziffer mehr gibt. Die Suchroutine also nicht mehr weiterkommt. Eine Sackgasse sozusagen. Die Routine macht das Feld wieder leer, beendet sich und gibt die Steuerung an die aufrufende Such-Routine zurück. Diese trägt versuchsweise die nächste mögliche Ziffer in ihr Feld ein und ruft die Such-Routine reentrant erneut für das nächste Feld auf. Oder sie beendet sich ihrerseits, wenn sie keine gültigen Ziffern mehr hat. Bei der Lösungssuche ergibt sich so also in der Regel eine Art länger andauernder Pump-Vorgang der aufgerufenen Such-Routinen mit den einzelnen Feldern und den verfügbaren Ziffern. Gepumpt wird dabei zwischen dem Ende einer Sackgasse und Beginn eines neuen Suchvorganges. Im besten Fall wird so zum Schluss genau eine Lösung gefunden. Fertig ist die Lösungssuche erst, wenn alle Sackgassen durchlaufen wurden, wenn also alle in Frage kommenden Möglichkeiten betrachtet sind. Der Durchlaufzähler zeigt während und nach dem Lösungsvorgang, wie oft die Such-Routine durchlaufen wurde. Reentrant Kurze Erklärungsversuch: Reentrant ist eine Eigenschaft, die ein Unterprogramm haben kann. Das Reentrant-Unterprogramm ruft sich selbst noch einmal auf. Unterprogramm? Was ist das? In diesem Zusammenhang ist es einfach nur ein mehr oder weniger abgeschlossener Programmteil, der normalerweise von einem Hauptprogramm aufgerufen wird, seine vorgesehene Funktion ausführt und wieder dahin zurückkehrt, wo es gestartet wurde. Nämlich ins Hauptprogramm. Es kann von verschiedenen Stellen im Hauptprogramm gestartet werden und kehrt immer wieder zurück, wo es hergekommen ist. Es ist mehrfach verwendbar und kann der Übersichtlichkeit und Effizienz dienen. Reentrant ist ein Unterprogramm, das sich selbst aufgeruft. Hört sich ziemlich verrückt an. Ist es wohl auch. Zumindest besteht die Gefahr einer unkontrollierten Vervielfachung. Das Programm wird immer größer, es wird einfach nicht mehr fertig. Die Geister, die ich rief, werd ich nicht mehr los. Ein Horrorszenario für Programmierer. Andererseits können Reentrant-Unterprogramme, auch einige Vorteile bieten. Die Suchroutine ist in diesem Fall ein Reentrant-Unterprogramm. Sie ist nur für ein Feld zuständig, ermittelt dort die möglichen Ziffern für dieses Feld, trägt im positiven Fall prophylaktisch eine Ziffer ein und ruft das gleiche Unterprogramm für das nächste Feld auf. Wenn die Such-Routine so zum 82. Mal aufgerufen wurde, braucht sie nur noch das vorliegende Ergebnis der abgelaufenen Suche zu verkünden. Die Kontrolle hatten die 81 vorher gestarteten Such-Routinen bereits für jedes der zurückliegenden Felder vorgenommen. Alle Felder enthalten dann einen gültigen Eintrag. Anderenfalls wäre es gar nicht zum 82. Aufruf der Such-Routine gekommen. Fazit: Manchmal ist ein zuverlässiger Lösungsweg mit einem einzigen Reentrant-Unterprogramm erreichbar. Der Web-Worker Abhängig von der Leistungsfähigkeit und Auslastung
des Computers kann die Berechnung einige Zeit in Anspruch nehmen.
|
|
|
letzte Aktualisierung |