Sudokus generieren – Teil 2

SudokuVor 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!

2 Responses to “Sudokus generieren – Teil 2”

  1. […] Buschtrommel (=bush telegraph) Software Reviews for PocketPC, XDA and MDA « Sudokus generieren – Teil 2 […]

  2. […] Hallo liebe/r Besucher/in, mit großer Wahrscheinlichkeit hast Du über eine Suchmaschiene oder die Mobile Sudoku-Seite hierhergefunden. Neben PocketPC-Anwendungen werden hier viele Tips und Tricks zum Thema Sudoku angeboten. Wenn du der Ãœberzeugung bist, dass sich hier, hier oder hier wertvolle Informationen finden, kannst du jetzt deine Stimme für die Buschtrommel abgeben! […]