Sudoku

[alzaimar]

Zitat von Grishnak:

Ich habe mich ebenfalls an einem (Multi-)Sudoku-Solver versucht. Das Programm errechnet per Backtrac(k)ing alle möglichen Lösungen.

Das ist überflüssig, weil es per definitionem sowieso nur genau eine Lösung für jedes Rätsel gibt.

Nur der Vollständigkeit halber hier meine Version. Es verwendet für jede Spalte, Zeile und 3x3-Quadranten die Menge der möglichen Zahlen.
Sei Z[i] die Menge der möglichen Zahlen, die in Zeile i vorkommen können, S[j] die analoge Menge für die Spalten und Q[i,j] Selbiges für den 3x3 Quadranten, in dem i und j liegt. Dann sind die möglichen Zahlen für Zelle[i,j] die Schnittmenge Z[i]*S[j]*Q[i,j].

Das Programm ermittelt zunächst eine Liste der freien Zellen und initialisiert die eben erwähnten Mengen. Dann prüft es im zweiten Schritt, ob für eine Zelle [i,j] die Schnittmenge aus genau einem Wert besteht--> Die Zelle kann gleich belegt werden. Dieser Schritt ist nicht notwendig, schränkt jedoch die Anzahl der Möglichkeiten u.U. sehr stark ein,

Abschließend wird per Backtracking (wirklich mit 'k') nach der Lösung gesucht. Beginnend mit der linken oberen Zelle werden nacheinander einfach alle Möglichkeiten, die sich aus den Schnittmengen ergeben, durchprobiert. Die SW sucht zwar weiter, nachdem eine Lösugn gefunden wurde, aber wie ich schon sagte, ist das bei echten Sudoku-Rätseln überflüssig.

Das Programm verwendet ein Beispiel-Rätsel und ist nur als Demo gedacht: Eine komfortable GUI ist nicht implementiert.