Buschtrommel OnlineMagazin

Hallo lieber Besucher, mit großer Wahrscheinlichkeit hast Du über den Suchbegriff „Sudoku“ hierhergefunden. Die Buschtrommel hat sich neben anderen Themen zur Aufgabe gemacht, schonungslose Aufklärung zum Thema Sudoku zu betreiben :). So ist sie eine der ersten deutschen Seiten, wenn nicht die erste überhaupt, die das Thema Symmetrie von Sudoku-Rätseln offen anspricht. Es wird verraten, mit welchen Techniken man Sudokus effizient generieren oder lösen kann. Wenn du der Ãœberzeugung bist, dass sich hier wertvolle Informationen finden, kannst du jetzt mit einem Klick auf das Bild links oben deine Stimme für die Buschtrommel abgeben und damit unsere Arbeit unterstützten.

Im letzten Eintrag wird von einer schnellen Methode berichtet Sudokus zu generieren. Diese hat allerdings einen Nachteil, wie mir jetzt aufgefallen ist. Sudokus, die vorher symetrisch im Bezug auf die aufgedeckten Zahlen waren, verlieren diese Eigenschaft. Nun stellt sich die große Frage, ob Sudokus per Definition symetrisch sein müssen. Die Rätsel der Zeitung „Zeit“ sowie das Beispiel auf Wikipedia weisen Symetrien auf. In der Definition auf Wikipedia wird dies jedoch nicht explizit erwähnt. Bei anderen Quellen findet man beides. Nimmt man beispielsweise die Menge der verfügbaren Sudokubücher so fällt schon bei der Betrachtung der Titelabbildungen auf, daß hier keine Einigkeit herrscht und die Sudokuwelt in etwa zwei gleich große Lager zerfällt.

Als eine weitere Autorität in Sachen Sudoku kann die japanische Zeitschrift Nikoli gesehen werden. Sie bietet lediglich symetrische Rätsel an. Andere Zeitungen (z.B. die österreichische Kronenzeitung) und viele der Hardware-Sudokugeräte verzichten auf die Eigenschaft.

Für die vorgestellte Methode ist jedoch nicht alles verloren. Dem Kobeleffekt tut die fehlendende Symetrie keinen Abbruch und nicht alle, aber bestimmte Folgen von Vertauschoperationen erhalten auch die Symetrie.

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!

Vor einiger Zeit habe ich an dieser Stelle über das Problem des Sudoku Generierens berichtet. Heute möchte ich einen Algorithmus zum Lösen vorstellen, wie er so ähnlich in Mobile Sudoku implementiert ist:

• Einfaches Einschränken – Man trage alle 9 Zahlen in jedes freie Feld ein und streicht all die, die in der Zeile, Spalte oder dem Teilbereich vorkommen.
• Zahl setzen – Wenn in einem Feld nur eine einzelne Möglichkeit verbleibt, trägt man diese als sicher ein und beginnt von vorne.
• Weiteres Einschränken – Kommen zwei Zahlen in einer Zeile (Spalte/Teilbereich) in zwei Feldern jeweils beide exclusiv vor kann man diese Zahlen aus allen anderen Feldern dieser Zeile (Spalte, Teilbereich) streichen.
  Analog geht dies für 3 Zahlen in 3 Feldern und 4 Zahlen in 4 Feldern…
• Einschränken Stufe Zwei – Kommen zwei Zahlen nur in zwei Feldern vor und in keinem anderen, so kann man alle anderen Zahlen aus den zwei Feldern streichen.
  Wiederum funktioniert dies analog für drei, vier und fünf Zahlen.
• Einschränken Stufe Drei – Kommt eine Zahl z in einer Spalte s (bzw. Zeile) eines Teilbereiches vor und ist aber für jede anderen Zeile des Teilbereiches ausgeschlossen, so kann man die Zahl aus allen Feldern der Zeile s außerhalb des Teilbereiches streichen.

Mit diesen Einschränkungsregeln solltet Ihr euer Sudoku in die Knie zwingen. Ansonsten ist es mit großer Wahrscheinlichkeit nicht eindeutig lösbar.