Sudoku - Info zur Online-Applikation


Zweck

Ein Sudoku ist eine Rätsel-Aufgabe, in der schon einige Felder mit Ziffern vorbelegt sind. Die Ziffern in den restlichen Feldern sind gesucht.

Mit dieser Online-Anwendung kann man Sudokus lösen, vor allem aber verifizieren, dass es nur eine Lösung gibt.


Bedienung

  • Maus:
    Feld aktivieren (blau)
    Feld deaktiviren (gelb)
    Button betätigen
  • Tastatur:
    Ziffer in aktiviertem Feld eingeben oder mit Leertaste löschen
    Cursor-Tasten zur Auswahl von neuem aktiven Feld
  • Touchpad:
    Button betätigen

Button "Try to solve" startet den Suchvorgang.

Wenn ein Ergebnis angezeigt wird, kann man mit Button "Back" zurück zur ursprünglichen Aufgabe.
Wenn mehrere Sudoku-Aufgaben geladen sind, geht man mit Button "Back" zurück zur vorherigen 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, mehrere 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:

  • Spitze Klammer zu, also Spitze nach rechts ">"
  • 81 Zeichen 1 - 9 oder Leerzeichen, für alle Sudoku-Felder oben links beginnend
  • Spitze Klammer auf, also Spitze nach links "<"
  • optional ein erklärender Text, der später im Auswahl-Button erscheint

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 allerdings nicht einfach. In den weitaus meisten Fällen endet ein Suchpfad damit, dass die Such-Routine 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 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ärung: 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 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. In diesem Fall ist die Such-Routine ein Reentrant-Unterprogramm, das nur für ein Feld zuständig ist, dort die möglichen Ziffern ermittelt, im positiven Fall prophylaktisch eine Ziffer in das Feld einträgt und das gleiche Unterprogramm für das nächste Feld aufruft. Wenn die Such-Routine also zum 82. Mal aufgerufen wird, 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. Und jedes dieser Felder enthält bereits 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 nur 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.
Zum Vermeiden sonst auftauchender Fehlermeldungen wird die Such-Routine des Sudoku-Lösers im Hintergrund mit einem Web-Worker ausgeführt, der seit einigen Jahren Bestandteil von JavaScript ist.


My Homepage

letzte Aktualisierung