Vor kurzem berichtete ich über eine Methode Sudokus zu generieren. Leider war der vorgestellte Algorithmus sehr zeitkomplex. Durch einen Benutzer von Mobile Sudoku wurde ich auf eine alternative schnelle und interessante Generierungsmethode aufmerksam gemacht.
Man geht von einer großen aber überschaubaren Menge von Sudokus aus, die man mit einem aufwändigeren Verfahren erzeugt hat. Diese „Ausgangspopulation“ von sagen wir 100 Rätsel kann man zu einer sehr großen Menge verschiedener Rätsel ausweiten indem man eine beliebige Anzahl folgender Mutationsschritte auf einem Rätsel durchführt:
- Vertauschen der Bockspalten: Im Beispiel vertauscht man den blau markierten Bereich mit dem grünen Bereich. Man erhält wiederum ein gültiges Sudoku.
- Vertauschen von Blockzeilen: Was oben für Blockspalten funktioniert, gilt ebenso zur Blockzeilen. Drei verschiedene Vertauschungen sind möglich.
- Vertauschen von Einzelspalten: Innerhalb einer Blockspalte kann man jeweils zwei Spalten vertauschen und alle Sudokuconstraints bleiben erhalten. Im Beispiel sind dies die rote und die gelbe Spalte.
- Vertauschen von Einzelzeilen: Keine große Überraschung. Die Sudokueigenschaften bleiben auch hier erhalten!
Auf diese Weise erhält man aus jedem Rätsel der Ausgangsmenge 3^10 neue Rätsel! Jippie!