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!


Warning: count(): Parameter must be an array or an object that implements Countable in /homepages/7/d34956116/htdocs/buschtrommel/wp-includes/class-wp-comment-query.php on line 405

2 Responses to “Sudokus generieren – Teil 2”

  1. Buschtrommel (=bush telegraph) » Blog Archive » Sudokus - symetrisch oder nicht symetrisch Says:

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

  2. Buschtrommel (=bush telegraph) » Blog Archive » Vote für die Buschtrommel! Says:

    […] 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! […]