Erst wollte ich
nie einen eigenen Sudoku-Löser schreiben, dann habe ich doch
einen implementiert. Zwar nur einige
logische Methoden, aber immerhin.
Dann wollte ich kein
Trial-and-Error-Verfahren vorsehen, aber auch hier bin ich mir jetzt untreu geworden. Es war ja so verlockend einfach:
Versuche zuerst ein Sudoku mit logischen Methoden zu lösen, soweit es geht. Als Ergebnis erhalte ich
(1) entweder ein nicht lösbares Sudoku,
(2) ein vollständig gelöstes Sudoku
(3) oder ein Sudoku, das sich nicht weiter mit den vorhandenen logischen Methoden lösen lässt.
Bei (1) gibt es keine Lösung des Sudokus, bei (2) habe ich eine Lösung gefunden, bei (3) tue ich das, was ich nie tun wollte: ich führe den Rechner in Versuchung.
Dazu lasse ich ihn die Zelle des teilgelösten Sudokus mit den wenigsten möglichen Lösungen finden. Diese Kandidaten werden dann einzeln durchprobiert. Nehme einen Kandidaten als Lösung für die Zelle an und versuche dieses teilgelöste Sudoku zu lösen - so wie bis hier beschrieben. Dazu verwende ich die gleiche Lösungsfunktion und erhalte eine klassische Rekursion.
An dieser Stelle habe ich als Ergebnis eines Einzelschrittes nur zwei Möglichkeiten:
(3.1) ein nicht lösbares Sudoku
(3.2) ein vollständig gelöstes Sudoku.
Teilgelöste Sudokus kommen nicht mehr vor, die Rekursion macht aus ihnen ein gelöstes oder ein nicht-lösbares Sudoku.
Bei (3.1) versuche ich mein Glück mit dem nächsten Kandidaten. Bei (3.2) habe ich eine von möglicherweise mehreren Lösungen gefunden. Zur Zeit beende ich in diesem Fall den Löser erfolgreich mit eben dieser Lösung.
Falls unter allen Kandidaten der einen ausgesuchten Zelle keine Lösung zu finden ist, gibt es keine Lösung für das gestellte Problem.
Es hat länger gedauert, diese Beschreibung des Algorithmus nieder zuschreiben als die Lösungsfunktion zu implementieren. Das liegt sicher daran, dass ich den bereits fertigen logischen Löser verwendet habe, und an ...
The Power of APL.
ap127
Noch einige Worte zu meinem Trial-and-Error-Funktion ... Mit wenigen Änderungen finde ich alle möglichen Lösungen zu einem Sudoku. Anstatt bei der ersten gefundenen Lösung (siehe 3.2) aufzuhören, kann man auch alle Kandidaten bis zum bitteren Ende
Aufgenommen: Jul 03, 23:34