Ein Sudoku zu lösen ist ein Unterfangen, welches durchaus einiges an Zeit beanspruchen kann. Ein Computerprogramm kann jedoch sehr schnell zu einer Lösung kommen. Gehen wir mal von den Fall aus, dass ein Programm ein neues Sudoku erstellen soll. Es gibt also keine vorausgefüllten Bereiche. Nehmen wir an die Größe des Sudoku sei 9×9 Felder.
Nun würde man im naiven Fall ein Generate-Test Prozedere implementieren, indem erst eine Version erstellt wird und dann geprüft wird, ob es sich bei den Ergebnis um ein gültiges Sudoku handelt. Im schlimmsten Fall läuft das Programm folgende Iterationen durch:
- 1. Feld: 9 Möglichkeiten
- 2. Feld: 9*9=81 Möglichkeiten
- 3. Feld: 9*9*9=729 Möglichkeiten
- …
- Letztes Feld (81. Feld): 981 ungefähr 2*1077 Felder
Das entspräche einer Rechenzeit von etlichen Jahren. Natürlich würde niemand solch ein Verfahren implementieren wollen. Nutzt man Constraint Programmierung, so kann man in wesentlich weniger Rechenzeit diese Berechnungen vornehmen. Damit lässt sich ein Test-Generate Verfahren programmieren. Es werden also erstmal die Regeln für ein gültiges Sudoku beschrieben und dann wird aus dieser Information ein Sudoku generiert.
Da mich die Programmiersprache Prolog sehr interessiert, habe ich in dieser Sprache ein Sudoku-solver programmiert. Neben der Lösung eines Sudoku und der selbst wählbaren Größe des Sudoku wird dann auch die Rechenzeit angegeben. Ein gegebenes Sudoku mit Größe 9×9 wird in weniger als 1 msec gelöst und ausgegeben. Ein Sudoku der Größe 36×36 Felder braucht etwa 400 msec. Ein Sudoku der Größe 64×64 Felder hingegen braucht schon 5 Sekunden. Dennoch ist diese Geschwindigkeit beeindruckend, wenn man die Datenmenge bedenkt.
Beispielaufruf:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | | ?- gen(Su, 9, 1). +------+------+------+ | 1 2 3| 4 5 6| 7 8 9| | 4 5 6| 7 8 9| 1 2 3| | 7 8 9| 1 2 3| 4 5 6| +------+------+------+ | 2 1 4| 3 6 5| 8 9 7| | 3 6 5| 8 9 7| 2 1 4| | 8 9 7| 2 1 4| 3 6 5| +------+------+------+ | 5 3 1| 6 4 2| 9 7 8| | 6 4 2| 9 7 8| 5 3 1| | 9 7 8| 5 3 1| 6 4 2| +------+------+------+ time_spent:0 msec for:sudoku(9) Sudoku no.: 1 Total amount of time: 0 msec Su = [[1,2,3,4,5,6,7,8,9],[4,5,6,7,8,9,1,2,3],[7,8,9,1,2,3,4,5|...],[2,1,4,3,6,5,8|...],[3,6,5,8,9,7|...],[8,9,7,2,1|...],[5,3,1,6|...],[6,4,2|...],[9,7|...]] ? yes | ?- |
Allgemein ist ein Aufruf:
Zur Berechnung des Sudoku wird hier die Bibliothek CLP/FD genutzt. Diese ist z.B. in der Distribution von SICStus Prolog enthalten.
Weiterführende Link:
- sudoku.txt (Prolog Quellcode – bitte in sudoku.pl umbenennen)
- http://www.sics.se/sicstus/