Buschtrommel OnlineMagazin

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 🙂

This entry was posted on Mittwoch, Dezember 14th, 2005 at 10:05 pm and is filed under Sudoku. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.