Sudoku

Eine Mich(e)ls-Seite vom Jahreswechsel 2005/06.

Sudoku ist ein Zahlenpuzzle, das zur Zeit gerade in Mode ist.

Das Spielfeld besteht aus einem 9x9-Quadrat, also aus 81 Feldern. Es ist nochmals in 9 Gebiete zu je 3x3 Felder unterteilt. Die Regel besagt, dass die 81 Felder so mit den Zahlen 1 bis 9 auszufüllen sind, dass in jeder Zeile, in jeder Spalte und in jedem 3X3-Gebiet jede Ziffer nur einmal vorkommt.

Die größte Kunst ist es, ein derartiges Super-Magisches-Quadrat zu entwerfen. Der Neuseeländer Wayne Gould kam zu Weltruhm dadurch, dass er ein Computerprogramm entwickelte, das in der Lage ist, Sudokus zu konstruieren. Viel, viel einfacher ist es, das Quadrat auszufüllen, wenn eine bestimmte Anzahl von Zahlen schon an der richtigen Stelle eingetragen sind. Man findet diese Rätsel jetzt in vielen Zeitschriften; es gibt auch schon Bücher mit Hunderten von verschieden schweren Sudokus. Im Internet findet man z.B. auf der Seite von Die Zeit jeden Tag ein neues Sudoku:

http://www.zeit.de/sudoku

Ich habe mir ein Sheet in Microsoft Excel entworfen, das es recht einfach macht, Sudokus am Bildschirm zu lösen (siehe Bild unten). Wohlgemerkt, die Lösung ist noch Handarbeit. Im Internet kursieren auch schon Programme, die das Lösen mehr oder weniger automatisch vornehmen (siehe auch unten mein Versuch "AutoSudoku.xls"). Das von mir hier angebotene Excel-Formular übernimmt nur die Funktion des Gedächtnisses. Besonders in der letzten Phase von schweren Sudokus ist aber immer noch Grübeln oder Probieren angesagt.

Ausgangspunkt ist in jedem Fall ein Leerformular, bei dem in jedem Feld alle neun Ziffern von 1 bis 9 stehen. Im ersten Schritt werden die vorgegebenen Felder mit den richtigen Ziffern belegt. Danach werden durch wiederholte Anwendung der Zeilen-, Spalten- und Gebietsregel alle Zahlen gelöscht, die für ein Feld nicht in Frage kommen. Das ist in der Anfangsphase eine eher monotone Konzentrationsübung. Bei leichten Sudokus gelingt es in dieser Phase oft schon, in manchen Feldern die Anzahl der Ziffern auf eine zu reduzieren.

In der zweiten Phase werden die Gebiete, Zeilen und Spalten daraufhin überprüft, ob eine der noch fehlenden Ziffern in den mehrstelligen Feldern nur einmal vorkommt, womit ihre richtige Stelle gefunden ist. Weitere Tips und die Schritt-für-Schritt-Anleitung stehen in der Excel-Datei , die Sie hier herunterladen können (Excel 97 ff.):

www.michls.de/troedel/sudoku.xls

In dem Beispiel im Bild wurde das dunkelgraue Feld ganz rechts in der Mitte gerade bearbeitet. D.h. in der 5. Zeile wurden alle 8 gelöscht, ebenso in der 9. Spalte und in dem 3x3-Gebiet, in dem das dunkelgraue Feld liegt. Für das gelb markierte Feld ist zwar schon sicher, dass dort eine 7 steht, aber die Sudoku-Regeln wurden dort noch nicht angewandt, d.h. in der 7. Zeile, der 9. Spalte und in dem Gebiet recht unten steht noch in mehreren Zellen 7. Der nächste Schritt wäre jetzt, das dunkle Feld mit der 8 hellgrau zu markieren, da es erledigt ist, dann das gelbe Feld mit der 7 dunkelgrau zu markieren und mit dem Löschen der 7 zu beginnen, z.B. in Zeile 7, Spalte 4 (279 wird 29) und Zeile 7, Spalte 6 (27 wird 2). Das Feld mit der 2 würde gleich gelb markiert als Merker, dass es später noch zu bearbeiten ist. Und so geht es weiter.

Die kleinen Zahlen am Rand des Quadrates und in dem separaten 3x3-Feld rechts sind die Summen über die Zeilen, Spalten und Gebiete. Die Summe aller Zahlen von 1 bis 9 ist 45. Bei 45 werden die entsprechenden Felder grün markiert (nur so als optischer Effekt).

Nachtrag vom 07.01.2006:

Automatische Sudoku-Lösung per Programm mit Excel-VBA

Es hat mich doch in den Fingern gejuckt, die oben beschriebene systematische Vorgehensweise zum Lösen von Sudoku-Rätseln in Microsoft Excel 97 als Programm in Visual Basic for Applications (VBA) zu schreiben. Das Ergebnis, das fast alle von mir ausprobierten Sudokus automatisch löst, kann mit dem Link weiter unten heruntergeladen werden. Überschreiben Sie einfach in den vorgegebenen Feldern die 123456789-Zahlenkette durch die vorgegebene Zahl, und lassen Sie ihrem PC eine Sekunde Zeit für die anschließende Neuberechnung. Standard-Sudokus sind gelöst, sobald Sie alle vorgegebenen Zahlen eingetragen haben. Macht das noch Spass?

www.michls.de/troedel/AutoSudoku.xls

(Keine Garantie für nix. Schimpfen Sie nicht, wenn es nicht funktioniert. Das ist keine Anwendung, die für verlässlichen Gebrauch ausgelegt und für alle Eventualitäten getestet ist. Es gibt z.B. keine Korrektur von Eingabefehlern. Bekanntes Problem: Wenn das Programm keine Lösung findet und Sie anschließend in ein Feld versuchsweise eine Zahl eingeben, dann passiert womöglich Quatsch. Wenn Ihre Zahl falsch ist, werden auch schon mal Felder mit Ziffern gefüllt, die den Sudoku-Regeln widersprechen, ohne dass eine Meldung ausgegeben wird. Ich hatte keine Lust mehr, den Fehler zu suchen. Optimierte Version siehe ganz unten.)

Mail-Rückmeldungen

Alternativer Tabellenentwurf für manuelle Lösungen

www.michls.de/troedel/SUDOKU-SUMO.xls



Hallo Herr Michels,

ich habe mich seit ein paar Tagen mal mit Sudoku beschäftigt und bin auf Ihre Homepage gestoßen. Beim Sudoku hatte ich mir vor allen Recherchen im Internet allein überlegt, für eine visuelle Lösung die Einzelzellen auf 3 x 3 Matrizen aufzubohren. Das sieht zwar etwas kompliziert aus; durch die optische einfache Verfolgung in Zeilen, Spalten und Unterquadraten ergibt sich aber eine vereinfachte und schnellere Lösung.

Sie sehen im Beispiel (aus dem Stern) oben das Leer- Formular, dann die vorgegebenen Zahlen, dann die Lösungszahlen in rot. Ich lösche die nicht zutreffenden Zahlen hierbei nicht, sondern setze nur die Hintergründe z.B. auf schwarz.

Also, Sudoku ist eher formal und nicht so wirklich kreativ, muss ich sagen.

Gruß und viel Spaß noch!

S. Frey

Getuntes AutoSudoku

www.michls.de/troedel/AutoSudokuSchober.xls



Hallo Leo,

als schon fast Sudoku-Süchtiger bin ich bei der Suche nach Abhilfe (es hat einfach zu viel Zeit gekostet) über Google auf Ihr AutoSudoku.xls gestoßen und war froh, ein Lösungsprogramm nicht selbst von Grund auf schreiben zu müssen.

Ein wenig der gesparten Zeit habe ich dann in ein paar Verbesserungen Ihrer echt schönen Vorlage gesteckt:

1.) Es gibt nun eine Prüfung, ob die errechneten Werte auch noch eine korrekte Lösung ergeben. Es wird gegebenenfalls eine Meldung mit Hinweis auf das Fehlerfeld ausgegeben.

2.) Es gibt jetzt mit „Save“ eine Möglichkeit, den aktuellen Stand wegzusichern (ohne Speichern des XLS) und über „Restore“ wieder zurückzuholen. Damit kann man bei Sudokus, die nicht direkt gelöst werden (siehe Beispiel, Zeit vom 24.8.2006), wo man also Probieren muss (Backtracking) einfach mal Speichern, in einem Feld eine der verbliebenen Möglichkeiten wählen und, wenn das zu einem Fehler (siehe Punkt 1) führt, einfach nach Restore den anderen Weg ausprobieren.

3.) Die Suche nach den doppelten Paaren war noch nicht ganz erschöpfend: Bisher wurde nur für das erste gefundene Paar geprüft, ob es noch einmal vorkommt, wobei dann in einer „Reihe/Gruppe“ z.B. 12, 23, 23, ...die doppelten 23 nicht gefunden wurden, weil nur auf doppelte 12 geprüft wurde. Mit einer kleinen Schleife mehr werden nun auch weitere Paare geprüft.

Genau genommen müsste man ja auch noch auf drei gleiche Drillinge prüfen, wobei in einem Feld sogar eine Ziffer fehlen könnte. Beispiel: Stehen in einer „Reihe/Gruppe“ 123,123,123 oder aber auch 123, 12, 123, so könnte aus allen anderen Feldern die 1, die 2 und die 3 genau wie bei den doppelten Paaren gestrichen werden. Da man ja auch so gut zur Lösung kommt (und damit die Sucht eingedämmt ist) habe ich das noch nicht implementiert. Und über die Varianten bei vier 4-tupeln (z.B. 1234, 1234, 134, 124) möchte ich lieber gar nicht nachdenken. Das wäre dann wohl fast schon eine neue Sucht :-)...

Wenn Sie möchten, können Sie die neue Version natürlich gerne auf Ihrer homepage updaten.

Vielen Dank für die verkürzte Suchtterapie und viele Grüße von

Martin Schober