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.

Wie löst man ein Sudoku…schwierig…wie erzeugt man ein gutes Sudoku … noch schwieriger, … wie erzeugt man ein Sudoku extrem schnell … richtig schwierig! Zuerst mal der Basisansatz:

1. Man erzeugt einfach eine korrekte Belegung eines 9×9-Feldes indem man von links oben nachts unten alle Felder durchgeht und in jedes Feld eine zufällige der noch erlaubten Zahlen einträgt. Kommt man mal nicht weiter trackt man back!
2. Jetzt bestimmt man zuällig x Felder die aufgedeckt sein sollen und löscht die restlichen Zahlen.
3. Ergebniss ist ein Sudoku nur leider ist noch nicht gewährleistet, ob es eine eindeutige Lösung hat. Dies erreicht man mit einem logischen Solver, der ähnlich kombiniert wie der Mensch es machen würde.

Ok das war ganz grob und nun zu den Detailproblemen. Was macht man, wenn im Schritt 3 rauskommt, es ist nicht mit reinem Schliessen ohne Raten oder Ausprobieren lösbar. Von vorne anfangen? Nein das wäre ja doof, das hat ja schon Rechenzeit gekostet die Ausgangsbelegung zu generieren und die ist ja noch gut. Eine neue Teilmenge offener Zahlen würfeln? Bei 48 und 36 offenen Zahlen funktioniert das gut. Hier hat man nach im Schnitt zwei Anläufen ein lösbares Rätsel gefunden. Bei schweren Rätseln der 24er-Kategorie ist die Wahrscheinlichkeit zufällig ein lösbares Rätsel zu treffen schon kleiner. Was nun? Ich hatte mir hier folgendes ausgedacht:

1. Man deckt eins der 24 vorgegebenen Felder wieder zu
2. Der Löser soll sehen wie weit er kommt. Lösung gefunden? Hurra!?
3. Falls nicht: Man nimmt eins der Felder die nicht vorgegeben waren und nicht erschlossen werden konnten und deckt es als vorgegeben auf. Wechsel zu Schritt 2

Diese Variante hat in meinen Experimenten einen Geschwindigkeitssteigerung m den Faktor 3 zur Folge. Weitere Kniffs und Tricks sind Betriebsgeheimniss 🙂

Ich habe mich heute entschlossen eine neue Artikelkategorie zum Thema Sudoku einzuführen. Eine Pressemitteilung von OpenPR hat mich auf ein 3-Dimensionales Sudoku aufmerksam gemacht.

Zwei Erfinder aus Deutschland haben die Idee des Sudoku-Rätsels mit dem Rubiks-Würfel gekreuzt und heraus kam ein Sudokuwürfel. Nette Idee und bestimmt ist es noch schwieriger als der alte Würfel mit den Farben, bei dem es schon Trillionen von Möglichkeiten gab. Verblüfft hat mich aber die Aussage daß die Idee mit einem Patent geschützt ist. Ich hätte spontan vermutet, dass das nicht geht. Immerhin hat Ernö Rubik aus Budapest ihn schon 1975 zum Patent angemeldet und soweit ich weiss gilt Patentschutz in Deutschland 20 Jahre. Desweiteren habe ich irgendwo mal aufgeschnappt, dass man Spiele nicht patentieren kann, sondern nur technische Lösungen für ein Problem. Verwirrung!