~ Sudoku Generator/Solver ~

17.09.2008 - Projekte

Aus lauter Langeweile habe ich im WK an einem Abend einen Sudoku Generator geschrieben. Das hat Spass gemacht, aber den Abend nicht gefüllt. Somit habe ich auch gleich noch einen Sudoku Solver geschrieben, der dann die generierten Sudukus wieder lösen durfte. Ein Perpetum Mobile so zu sagen ;-)

Sudoku Generator

Mein Sudoku Generator beruht auf einer einfachen eigenschaft von Sudokus: Zwei Spalten, bzw. zwei Zeilen lassen sich vertauschen ohne die Regeln von Sudoku zu verletzen, solange sie die innerhalb eines Drittels vertauscht werden, d.h. Spalten/Zeilen 1-3, 4-6 und 7-9 dürfen beliebig vertauscht werden. Beginnt man nun mit einem "banalen" Sudoku, welches in jeder Zeile die Zahlen 1-9 jeweils um 4 nach rechts verschoben enthält (gegenüber der oberen Zeile), und tauscht genügend lange, zufällig jeweils zwei Spalten und Zeilen, so erhält man ein "zufälliges", jedoch bereits ausgefülltes Sudoku. Nun braucht man nur noch eine beliebige Anzahl Felder zu löschen - je mehr desto schwieriger ist das Sudoku zu lösen.

um vier neue Sudokus zu erzeugen.

Sudoku Solver

Der Sudoku Solver löst das vorgegebene (oder auch leere) Sudoku rekursiv nach der Brute-Force-Methode: Es wird pro leeres Feld einfach die Zahlen 1-9 eingesetzt und jeweils getestet ob eine der Sudoku-Regeln verletzt wurde. Falls Nein, gehts weiter zum nächsten leeren Feld. Falls Ja, wird die nächste Zahl versucht. Falls keine Zahlen von 1-9 is leeren Feld passt, kommt es zum Backtracking zum vorherigen leeren Feld und dort wird die nächstmöglichen Zahl ausprobiert, bis das ganze Sudoku gelöst ist.

Zahlen in die leeren Feldern eingeben und dann "Sudoku Lösen" klicken.