... ein Sudoku lösen: Ohne Versuch und Irrtum, nur durch logisches Kombinieren oder Ausschließen von Lösungen. So gehen menschliche Sudoku-Löser an die Sache, solange bis es mit diesen Methoden nicht weitergeht.
Nachdem ich
meine Darstellung eines Sudokus bzw. seiner möglichen Lösungen im APL festgelegt hatte, habe ich verschiedene "logische"
Lösungsmethoden implementiert. Nicht alle, aber die einfachsten und wichtigsten, da mit ihnen alle leichten, mittel- und die meisten schweren Sudokus lösbar sind. Die dazugehörigen Funktionen heißen FILL, SCAN, ELIM, ELIMB und PAIR.
Jede dieser Funktionen wendet eine spezifische Methode nacheinander entlang der Zeilen, der Spalten und Blöcke an. Dafür ist jeweils nur eine Implementierung nötig. Denn die Anwendung einer Methode auf die Zeilen eines Sudokus ist das gleiche wie die Anwendung der Methode auf die Spalten des zugehörigen transponierten Sudokus. Das gleiche gilt für Zeilen und Blöcke (wegen Transitivität dann auch für Spalten und Blöcke) .
Dafür war die Darstellung einer Sudoku-Lösung als logische
Matrix vom Rang 5 gedacht.
Jede Lösungsfunktion erwartet als rechtes Argument diese Lösungsmatrix und liefert als explizites Ergebnis eine solche. So kann ich beliebige Sequenzen von Lösungsfunktionen bilden:
RESULT PAIR SCAN ELIM SCAN FILL START sudoku
oder
RESULT SCAN ELIM PAIR ELIM START sudoku
Manche Sudokus lassen sich erst durch Anwendung der X-Wing-Methode lösen (oder natürlich durch Trial-and-Error). Mit einer Implementierung dieser Methode kann die erste Sequenz - soweit sie nicht bereits zum Ziel geführt hat - wie folgt erweitert werden:
RESULT SCAN XWING SCAN PAIR SCAN ELIM SCAN FILL START sudoku
Mit solchen Sequenzen experimentiere ich nun schon eine Weile herum, um so etwas wie eine optimale Anwendung von logischen Methoden zu finden.
ap127
Das ist so nicht ganz korrekt. Es sollte heißen: Alles oder Ein. Ich weiß, Das ist kein Deutsch! "Alles" meint Folgendes: Natürlich habe ich alle vorhandenen Lösungsfunktionen in einer Funktion verpackt, so dass ich mit einem Funktionsaufruf ein Su
Aufgenommen: Apr 10, 17:05
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 geword
Aufgenommen: Jul 02, 23:30
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