Generate Sudoku
If you read the section on solving Sudoku you know now how to solve Sudoku. But how are they generated?
There is no simple algorithm for generating Sudoku, you have to use trial and error most of the time.
Doing this manually is a tedious and error-prone taks, so usually you let a computer do the task.
Bottom-Up Method
A rather simple but nonetheless successfull approach starts from an empty Sudoku grird:
- Fill your empty grid with about 25 numbers randomly and take care not to violate any Sudoku rules while doint this, i.e. don't fill the same number twice into a single row, column or block.
- Use a Sudoku Solver to check whether the generated Sudoku is solvable and has a uniq solution.
- If it is not solvable, discard you current Sudoku and start anew.
- If it is ambigous go on adding numbers randomly.
As soon as a Sudoku has only one uniq solution, you're done.
A simple generator using this technique needs 27 milliseconds on average on my Laptop to generate a fairly hard Sudoku.
The last step can be varied in order to achieve better performance: instead of adding numbers randomly you can use a solver that picks one of the possible solutions and copies correct numbers from this solution to generated Sudoku.
This modification ensures that very few Sudokus have to be discarded.
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:
- 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.
- 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.