Skip to main content.

Sudoku Generieren

Wenn Sie sich den Abschnitt über das lösen von Sudokus durchgelesen haben, wissen Sie, wie man Sudokus löst. Aber wie erstellt man sie?

Die Antwort ist, dass es kein Patentrezept gibt, und alles letztendlich auf ausprobieren hinausläuft.

Da das von Hand eine sehr aufwändige und fehleranfällige Arbeit wäre, lässt man es einen Computer machen.

Bottom-Up-Methode

Die einfachste Möglichkeit ist folgende, die von einem leeren Feld ausgeht:

  1. Man füllt etwa 25 Zahlen zufällig in ein leeres Sudoku-Gitter, und achtet dabei darauf, dass man keine der Sudoku-Regeln verletzt (d.h. keine zwei gleichen Zahlen in der selben Zeile, Spalter oder im gleichen Block).
  2. Man überprüft mit einem Solver, ob das entstandene Sudoku lösbar und eindeutig ist.
  3. Wenn es nicht lösbar ist fängt man wieder von vorne an.
  4. Wenn es mehrdeutig ist, fügt man solange zufällig weiter Zahlen hinzu bis es eindeutig ist.

Sobald ein Sudoku nur noch eine Lösung hat, ist man fertig.

Auf meinem Laptop braucht ein solches Programm im Durchschnitt 27 Millisekunden, um ein Sudoku zu erzeugen, es ist also für fast alle Anwendungen schnell genug.

Eine Variation des letzten Schritts ist es, eine beliebige Lösung des Sudokus zu nehmen und zufällig eine Zahl aus dem gelösten auf das neue Sudoku zu kopieren. Damit vermeidet man sehr viele unlösbare Sudokus.

Top-Down-Methode

Man kann auch ein Sudoku erzeugen, indem man von einem vollständig gelösten Sudoku ausgeht, und solange Zahlen entfernt, bis es mehrdeutig wird, und dann den letzten Schritt rückgängig macht.

Diese Methode hat den Vorteil, dass keinerlei ungültige Sudokus entstehen.

Sie hat aber auch zwei Nachteile:

  1. Man benötigt erst ein vollständig gelöstes Sudoku. Das kann man z.B. erstellen indem man ein paar Zahlen zufällig in ein Gitter füllt und eine beliebige Lösung nimmt. Damit hat man aber quasi auch wieder den Bottom-Up-Ansatz von vorher verfolgt.
  2. Wenn man einen Sudoku-Solver hat, der Buch führt, welche Zahlen wo erlaubt sind, ist es sehr viel leichter Zahlen hinzuzufügen als Zahlen zu entfernen.