In den Osterferien bin ich endlich dazu gekommen, mein kleines Sudoku-Lösungsprogramm zu schreiben, und es funktioniert schon in der jetzigen Version ausgezeichnet. Bisher tut es nichts weiter, als für jedes Kästchen im Sudoku eine Liste der noch möglichen Zahlen zu verwalten: jedes Mal, wenn eine neue Zahl irgendwo in ein Kästchen eingetragen wird, wird diese Zahl in allen Kästchen derselben Zeile, derselben Spalte und desselben Blocks aus der Liste entfernt. Das ist das Hauptprinzip.
Wie hilft mir diese einfache Listentabelle* die Lösungszahlen zu finden?
Naja: zum Einen kann ich alle Kästchen durchlaufen und mir ihre Listen anschauen. Wenn ich eine Liste finde, die nur noch eine Zahl enthält, dann ist in diesem Kästchen auch nur noch diese eine Zahl möglich, weil alle anderen Lösungen schon in andere Kästchen in Zeile, Spalte oder Block eingetragen worden sind. Diesen Treffer trage ich ins Kästchen ein (und aus den Listen drumherum aus), und dann kann ich schauen, ob ich noch weitere eindeutige Listen finde.
Was mache ich, wenn es irgendwann keine eindeutigen Treffer mehr gibt, weil sämtliche Listen mehrere mögliche Lösungszahlen enthalten? Dann kommt die zweite Methode ins Spiel: ich gehe alle Zeilen, Spalten und Blöcke durch und schaue, ob hier (in Zeile/Spalte/Block) eine Zahl in nur einer Liste vorkommt. Das entsprechende Kästchen ist dann die einzige Möglichkeit, diese Zahl in dieser Zeile ( oder Spalte oder Block) legal unterzubringen. Treffer eintragen, Trefferzahl aus Anliegerlisten streichen, weiterschauen.
Wie gesagt: das funktioniert ausgezeichnet. Bisher habe ich noch kein Sudoku gefunden, was ein Skript mit diesen beiden kleinen Funktionen nicht knacken konnte. Es funktioniert sogar so ausgezeichnet, dass ich hochgradig irritiert bin, weil ich beim Von-Hand-Lösen häufig noch einen weiteren Algorithmus verwenden muss, um Mehrdeutigkeiten aufzulösen. Bedeutet das, dass ich bisher beim Testen nur irgendwelche Popel-Sudokus gefunden habe und seither einfach keine richtig kniffligen mehr in der Zeitung stehen, oder bedeutet das, dass ich beim Von-Hand-Lösen dauernd Sachen übersehe und Flüchtigkeitsfehler mache?
Grmpf.
Ich gehe bis auf Weiteres erstmal davon aus, dass Sudokus seit den Osterferien einfacher geworden sind.
;-)