Spiele -- Sudoku

Überall ist das Sudoku-Fieber ausgebrochen. Deshalb habe ich ebenfalls einen Sudoku-Löser gebastelt. Meine Variante ist ein einfaches Commandline-Programm und regelbasiert, löst ein Sudoku also wie ein Mensch. Dazu gibt es ein Web-Frontend über das man das Sudoku-Rätsel eingeben kann um es lösen zu lassen.

Zum Sudoku-Löser hier klicken!

Die Eingabe

Die Eingabe für den Löser ist sehr einfach gehalten:

Es ist einfach nur ein Text der von links nach rechts und oben nach unten die Positionen des Sudoku-Felds beschreibt. Dabei steht die Zahl für die Zahl und ein Punkt (.) für ein nicht belegtes Feld. Dazwischen können sich beliebig Leerzeichen oder Zeilenwechsel befinden.

Außerdem kann man über ein kleines Wahlfeld einstellen, wie ausführlich die Lösung dokumentiert werden soll. 1 (default) ist jeden Schritt einzeln anzeigen. 0 überspringt eine mehrfach angewandte Regel und gibt nur die letzte Regel aus. -1 liefert lediglich das Ergebnis ohne die Schritte zu erläutern. (Derzeit wird immer die volle Ausgabe angezeigt, d. h. der Schalter wäre immer auf 1.)

Um es einfacher zu machen gibt es eine Ausfüllhilfe, die den Text erstellt. Ich finde die Eingabe direkt ins Textfeld bequemer, wer sich aber nicht sicher ist kann die Ausfüllhilfe verwenden:

• Die Positionen einfüllen an denen sich Zahlen befinden.
• Leere Felder einfach leer lassen.
  
• Dann "Übertragen" anklicken.
  
• Damit erscheint das Sudoku im Textfeld.
  
• Nun kann man "OK" anklicken und das Textfeld an den Löser schicken.

Hat man das Sudoku (evtl. über die Eingabehilfe) im Textfeld, drückt man "OK", dann läuft der Sudoku-Löser los.

Der 2. Weg

Derzeit gibt es ihn noch nicht. Der 2. Weg (wird ausgelöst wenn man den entsprechenden Button drückt) arbeitet mit Zahlfarben. Dieser Weg löst jedes mögliche Sudoku und findet auch die Lösung von nicht-eindeutigen Sudokus (also solche, die mehrere Lösungen besitzen). Mehr dazu weiter unten.

Sudokus klauen

Per Kopieren und Einfügen lassen sich Sudokus von anderen Seiten "klauen". Der Sudoku-Löser eliminiert dabei den "Kopiermist" der sich dabei eingeschlichen hat und guckt, ob ein sinnvolles Sudoku dabei herauskommt. Folgende Seiten funktionieren:

• www.sudoku-knacker.de/ Man markiert mit der Maus das Sudoku von unten nach oben, wobei man im "0 mal geprüft" ansetzt (irgendwo in dem Text) und dann die Maus so weit nach oben links zieht, bis das gesamte Feld mit der ersten Zahl markiert ist, aber nichts darüber (also insbesondere nicht der Kopf der Feldnummer und den Sternen). Dann über das Clipboard diese Markierung in das Textfeld von meinem Löser kopieren. Hat man richtig markiert wird das Sudoku nach Drücken von "OK" korrekt erkannt.

Hinweis: Man kann es so auch wunderbar ausdrucken. Man sucht sich einfach den Stand, in dem die Regel 1 in Folge das letzte Mal angewendet wird, und drückt dort "Print". Damit hat man ein "vorevaluiertes" Sudoku von dem man aus bequemer lösen kann (ich finde die ersten Schritte immer die Zahlen wegzustreichen als ermüdend und wenig erquicklich).

Die Ausgabe

Der Löser kennt keine tolle graphische Ausgabe (das Web-Frontend peppt diese einfache Ausgabe aber etwas mit Hintergrundfarbe auf). Es erscheint einfach nur Text der hintereinander die einzelnen Lösungsschritte ausgibt. Dabei wird per Text auch der jeweilige Stand des Sudoku-Feldes eingeblendet.

Beim Lösen wird die Anzahl der Durchläufe gezählt ("Lauf"), dazu wird die verwendete Regel angezeigt ("Regel") sowie wie oft die Regel hintereinander angewandt wurde ("Schritt"). Am Ende nach dem Lösen wird nochmals ausgegeben, wie oft welche Regel zur Anwendung kam.

Vorbelegte Zahlen werden mit einem Underscore (_) markiert. "Gelöste" Zahlen werden mit einem Gleichheitszeichen (=) markiert. Das Feld bzw. die Region auf die sich der aktuelle Schritt bezieht werden mit 4 Sternen (*) pro Kästchen markiert.

In den Feldern die noch nicht gelöst sind, erscheinen die möglichen Zahlen eintragbaren Zahlen. Der Löser geht dabei wie ein Mensch nach einer Regel-Liste vor um das Sudoku zu lösen. Er hat allerdings den Vorteil, dass er die komplexe Regel 5 mit Leichtigkeit anwenden kann.

Beispiel eines angezeigten Lösungsschritts:

Die Webausgabe sieht etwas farbiger aus, kann ich hier nicht darstellen. Außerdem gibt es zwei Links hinter jedem Lösungsschritt, der erste erstellt eine Druckausgabe die das Sudoku-Feld so anzeigt, dass man es zum Selber-Ausfüllen leicht drucken kann.

Der andere Link (SUDOKU) übernimmt die aktuelle Stellung wieder in die Eingabe, erzeugt also sozusagen den Sudoku-Stand.

Die Regeln

• Regel 0: Dies ist die "Lösungsregel". Sie erkennt, ob das Sudoku fertig ausgefüllt ist bzw. nicht mehr lösbar ist da ein Feld keine Zahl mehr beinhalten kann.
• Regel 1: Dies ist die normale Streichregel. Sie streicht diejenigen möglichen Zahlen aus einem Kästchen, die dort nicht stehen können, da diese Zahlen bereits in der Zeile, Spalte oder Region (dem rechteckiger 3x3-Bereich) vorkommen.
• Regel 2: Wenn in einem Kästchen (z. b. im Beispiel die einzelne 8 in Feld 9,6) nur eine mögliche Zahl verblieben ist setzt diese Regel diese Zahl ein. Sie stellt damit eine starke Vereinfachung der Regel 5 dar (der einer-Fall).
• Regel 3: Wenn in einer Zeile, Spalte oder Region eine Zahl nur noch in einem einzigen Feld vorkommt wird das Feld mit dieser Zahl belegt. Diese Regel ist so gesehen eine stark vereinfachte Regel 4, eben nur bezogen auf ein einzelnes Feld. (In obigem Beispiel steht im Feld 7,4, also das obere linke Feld der unteren mittleren Region, eine 6, sie kommt in keinem anderen Feld der Region vor, auch nicht in der Zeile, also muss in dieses Feld die 6.)
• Regel 4: Wenn in einer Schnittmenge einer Zeile oder Spalte mit einer Region eine Zahl derart vorkommt, dass sie in dem Rest der Zeile, Spalte oder Region (also dem Teil ohne die Schnittmenge) nicht ist, muss sie sich irgendwo in der Schnittmenge befinden. Dadurch kann sie in der zum zur Schnittmenge disjunkten Teil der Vereinigungsmenge eliminiert werden. (Mengenlehre.) Oder anders gesagt: Findet man einen 3er-Bereich in dem eine Zahl liegen muss, da sie in einer der möglichen Überdeckungen nicht befindet, dann kann man sie aus der anderen Überdeckung (aber nicht aus dem 3er-Bereich!) streichen, da sie ja im 3er-Bereich liegen muss, also nirgends außerhalb liegen kann. In der Ausgabe wird übrigens der 3er-Bereich markiert. Diese Regel entspricht der allgemeinen Regel 3, denn für eine einzelne Zahl die alleine vorkommt gibt es immer auch eine solche 3er-Überdeckung. Für den Menschen ist diese Regel noch gut anwendbar.
• Regel 5: Diese Regel ist die komplizierteste, besonders da der Computer leicht eine 4-Permutation findet, der Mensch aber schon für eine 3-Permutation lange suchen muss. Diese Regel besagt: Hat man N Kästchen (die innerhalb einer Zeile, Spalte oder Region liegen) für die es genau N mögliche Zahlen gibt, dann kann man in den anderen Kästchen (derselben Zeile, Spalte bzw. Region) all diese N Zahlen streichen sofern sie dort noch als möglich stehen. Es ist dann nämlich so, dass die N Zahlen in eben jenen N Kästchen stecken müssen. Wäre eine Zahl woanders, könnte man die Kästchen nicht mehr komplett ausfüllen, da dann für N Kästchen nur N-1 Zahlen zur Verfügung stünden. Technisch ist das gelöst, indem der Computer rekursiv absteigt und somit alle möglichen Permutationen der Kästchen durchprobiert. Der Mensch findet das so nicht, sondern wird das erst nach einigem Üben (oder durch Zufall) finden, besonders wenn N 4 oder höher ist.

Ich gehe davon aus, diese Regeln sind vollständig. Wenn ein Sudoku mit diesen nicht lösbar ist, dann ist es extrem schwer, d. h. man benötigt Backtracking, d. h. Spekulation und evtl.e Rücknahme des Zuges. Der Sudoku-Löser von mir unterstützt derzeit kein Backtracking, sondern löst nur nach den Regeln. Wenn das Sudoku dann nicht lösbar ist, ist es kein gutes (oder ein extrem schweres) Sudoku, da der Mensch selten mehrere Blätter hernehmen will um ein Sudoku zu lösen.

Lernen durch den Löser

Ich empfehle, das Sudoku so weit zu lösen wie man selber kommt. Bleibt man stecken kann man es in den Sudoku-Löser eingeben und nachschauen, was dieser tut. Als erstes wird er die einfachen Regeln anwenden, und so alles nachfahren, was man leicht übersehen kann.

Dann wendet er wahrscheinlich Regel 4 oder 5 an. Indem man die Ausgabe ansieht kann man diesen Schritt nachvollziehen (hoffendlich, es ist etwas Grips notwendig!) und daraus lernen. Natürlich kann man den Sudoku-Löser auch verwenden um ein Sudoku zu lösen, aber das ist ja eher langweilig.

Ich habe ihn programmiert, um genau die oben zitierten Regeln herauszufinden und programmatisch umzusetzen. Benötigt werden eigentlich nur Regeln 1, 4 und 5, aber für den Menschen sind die Regeln 2 und 3 leichter verständlich als (entsprechend) Regel 5 und 4. Da man "Negation" leichter findet als "Permutation" kommt Regel 5 zuletzt. Aufgrund von Regel 1 (Streichregel) findet man Regel 2 am leichtesten, aber Regel 3 springt einem ebenso nach kurzer Zeit ins Auge.

Interessant ist, dass es viele Sudokus gibt, die alleine durch Regeln 1 bis 3 gelöst werden können. Ich würde diese als sehr leicht bezeichnen, die mit Regel 4 als leicht bis mittel und alle die Regel 5 dazunehmen als mittel (perm 2), schwer (perm 3) oder sehr schwer (perm 4 und darüber).

Extrem schwer würde ich Sudokus bezeichnen, die sich ausschließlich durch Raten finden lassen. Das sind die, die dieser Löser derzeit nicht lösen kann (genausowenig wie Sudokus mit mehr als einer Lösung).

Ich habe aber vor, den Löser um ein Backtracking zu erweitern, das losläuft sobald alle Regeln ausgeschöpft sind. Sobald das der Fall ist kann dieser Löser alle lösbaren Sudokus lösen sowie bei allen nichteindeutigen Sudokus alle mögliche Lösungen ermitteln. Noch ist es nicht so weit.

Sourcecode

Der Sourcecode vom Sudoku-Löser ist verfügbar. Achtung, die Ausgaben sind in Deutsch! Er unterliegt der GPL.

Der 2. Weg: Sudoku und Zahlfarben

Folgende Lösung ist rein theoretisch, d. h. ich habe sie nicht implementiert, aber es sollte "mathematisch vollständig" sein. Sie stellt eigentlich eine optimierte Lösung von "Brute Force" dar, d. h. sie liefert immer alle möglichen Lösungen, aber ohne "dumm" jede beliebige mögliche Zahlenkombination durchzuprobieren.

Diese Methode löst Sudokus auch ohne eine richtige Regel (außer den typischen Sudoku-Regeln). Die Methode bedient sich etwas, das ich als "Zahlfarben" bezeichne. Die Idee ist sehr einfach:

• Man schreibt wieder alle 9 Zahlen in die freien Kästchen, nur diesmal nimmt man dafür zuerst einen Bleistift.
• Man radiert alle nicht möglichen Zahlen aus. Das ist so gesehen zwar irgendwie eine Regel (die Regel 1 von oben), aber man muss das nicht tun, denn die Zahlen bleiben einfach dann schwarz. Nur ist das sehr unübersichtlich, also ist radieren einfacher.
• Dann nimmt man einen Buntstift (man braucht sehr sehr viele und muss ein gutes Farbsehen haben) und radiert eine Zahl aus und zeichnet sie mit dem Buntstift nach. Außerdem umringelt man diese Zahl.
• Dann sucht man sich eine andere Zahl, die durch diese Zahl "bedingt" wird, d. h. in einem anderen Kästchen stehen muss wenn sich die (mit dem momentanen Stift) bunt markierte Zahlen in den Kästchen befinden würden. Solche neu gefundenen (eindeutigen) Zahlen umringelt man nicht, gibt ihnen aber die gleiche Farbe. Das wiederholt man so lange, wie man solche Zahlen findet (das können 0 sein)!
• Trifft man beim Verfolgen der vorherigen Bedingung wieder auf die Anfangszahl, dann umringelt man alle Zahlen die diesen Weg beschreiben (weil sie sich alle gegenseitig bedingen). Dies ist allerdings eher selten der Fall.
• Manchmal gibt es keine weitere Zahl die "bedingt" wird, dann legt man den Buntstift weg und nimmt einen anderen und fängt eben mit einer neuen Zahl an (einer die noch nicht farbig ist) und umringelt sie wieder, usw.
• Manchmal gibt es einen Widerspruch. Z. B. markiert man gerade mit orange und stellt fest, dass man dann in einem der Bereiche zwei gleiche Zahlen ebenfalls orange markieren muss was nicht möglich ist (jeder Bereich hat ja alle Zahlen nur exakt einmal). In diesem Fall kann man die Farbe verwerfen, das bedeutet, man entfernt die Farbe von allen Zahlen die diese (hier orange) farbige Markierung hatten, die mit der Farbe umringelten Zahlen können dabei garantiert in einer Sudoku-Lösung nicht vorkommen (da sie zum Widerspruch führen). Wichtig ist, nicht alle nur in der Farbe gemalten (also nicht-umringelten) Zahlen kann man nicht streichen, da diese nicht unbedingt zum Widerspruch führen. Einige wird man trotzdem streichen können weil von ihnen ebenso der Fehler ausgeht. Wahrscheinlich ist das aber viel zu unübersichtlich, also nimmt man die Farbe einfach wieder ganz weg und nimmt eine neue.
• Zwischendurch kann es vorkommen (beispielsweise: man markiert gerade blau) dass eine bereits farbige Zahl (beispielsweise: rot) bedingt wird. Es gibt dann zwei Fälle:
  • Die rote Zahl ist umringelt. In diesem Fall bedingt jede umringelte blaue Zahl jede rote Zahl. In diesem Fall bedingt Blau also Rot. Das merkt man sich (oder man macht jede rote Zahl blau).
  • Die rote Zahl ist nicht umringelt. Also bedingt sie nicht alle roten. In diesem Fall muss man sie ebenfalls blau markieren (z. B. durch ein Kästchen, nicht umringeln, denn das merkiert ja etwas anderes). Die roten nicht umringelten Zahlen können dann weitere Kandidaten für blaue Markierung ergeben.
• Das vollzieht man so lange, bis alle Zahlen "bunt" umringelt sind oder ausgeschlossen (am besten wegradiert) wurden.
• Nun hat man alle Lösungen indem man auf die Farben (und die Abhängigkeiten) guckt (die umringelten Zahlen helfen beim finden). Eine Farbe (mit den Abhängigkeiten) muss in jedem Feld sein (schließlich hat man jede Zahl mit einer Farbe versehen).
• Gibt es keine Farbe die in jedem Feld vorkommt, gibt es entweder keine Lösung, das Sudoku hat mehrere Lösungen, oder man hat noch nicht alle Abhängigkeiten gefunden die eine Zahl "bedingen" (in einem eindeutigen Sudoku gibt es die immer, anderenfalls wäre es nicht eindeutig).
• Ich dachte mir übrigens in einer alten Version des Textes hier, es gäbe unabhängige Unterbereiche von Farben. Das ist aber falsch. Es gibt die Möglichkeit, dass orange und blau sich gegenseitig ausschließen, aber orange nur mit lila und gelb kombinierbar ist während blau nur mit lila und grün kombinierbar ist.
• Mit etwas knobeln findet man durch die Farbgebung die Lösung leichter. Siehe dazu die "Anwedung für den Menschen".
• Eindeutige Sudokus haben dann (mit Abhängigkeiten) immer nur eine Farbe als Lösung. Das bedeutet, es gibt genau eine Farbe, die sich (mit ihren "bedingten" Zahlen) durch alle Felder zieht.

Es kann sein, dass man 20 oder 30 Farben benötigt. Leider gibt es nicht so viele gut unterscheidbare Buntstifte. Der Computer kann diesen Weg aber leicht beschreiten, da er unendlich viele "Farben" zur Verfügung hat die er unterscheiden kann (er zählt sie einfach durch).

Leider kann man aus diesem Weg aber nichts lernen. Er funktioniert ohne jede richtige Inspiration, ist einfach nur "stupide Arbeit". Dafür löst eine Computerimplementierung (im Gegensatz zu meinem Sudoku-Löser) jedes Sudoku ohne zu raten (da er ja eigentlich immer rät bis keine Zahl mehr da ist die er nicht erraten kann, im schlimmten Fall wird der volle Brute-Force durchgeführt).

Anwendung für den Menschen

Ich verwende Farbe immer dann, wenn ich beim Sudoku-Lösen nicht weiterkomme:

• Also zuerst löse ich wie mein Sudoku-Löser mit den oben aufgeführten Regeln 1 bis 5.
• Wenn ich dann nicht weiterkomme suche ich mir ein Feld, das mir geeignet erscheint. Meist ist das ein Feld für das es nur 2 mögliche Zahlen gibt.
• Die eine Zahl umringle ich rot, die andere blau.
  
• Dann versuche ich das Sudoku in der "roten" Variante zu lösen (also als ob die blaue Zahl nicht da wäre, im Kästchen also die rote Zahl stünde). Alle Änderungen (also Zahlen für die ich Abhängigkeiten finde) werden dabei rot. (aber nicht umringelt!)
• Stoße ich auf eine rote Zahl, die dabei die umringelte rote Zahl bedingt, dann wird diese auch umringelt.
• Stoße ich dabei auf einen Widerspruch, also ein Kästchen in dem es dann keine mögliche Zahl mehr gibt, oder zwei Zahlen rot angemalt werden müssten, dann weiß ich, dass die rote Zahl nicht stimmt und es die blaue sein muss!
• Wenn ich nicht weiterkomme dann mache ich mit der blauen Variante weiter. D. h. ich tue so, als wären rot umringelte Zahlen nicht da (ja, alle, die ich umringeln konnte).
• Die so gefundenen Zahlen werden dann blau angemalt.
• Stoße ich auf eine Zahl, die bereits rot ist und jetzt zusätzlich blau werden müsste, weiß ich, diese muss auf jeden Fall in der Lösung sein (denn sowohl rot als auch blaub bedingen diese Zahl).
• Stoße ich auf ein Kästchen, in dem bereits eine andere rote Zahl ist, dann weiß ich, dass in diesem Kästchen keine anderen Zahlen als die beiden (rot bzw. blau) vorkommen können (denn eine dritte Farbe ist nicht möglich, das Ausgangskästchen hatte ja nur 2 Zahlen, also nur 2 Farben)!
• Stoße ich auf einen Widerspruch in Blau, weiß ich, dass die rot umringelten Zahlen gelten müssen.
• Auf diese Weise kann man oft mögliche Zahlen eliminieren und so über die Regeln 1 bis 5 weitere Kästchen mit ihren Zahlen erhalten.
• Und wenn es kein Kästchen gibt, das 2 Zahlen enthält, muss man eben 3 Farben verwenden und alles oben entsprechend um die 3. Farbe erweitert anwenden.

Wenn das dann immer noch nicht weiterhilft, suche ich mir eben ein weiteres Kästchen das mir geeignet erscheint, und nehme andere Farben. Oft stelle ich dann fest, dass ich mit einer der Farben auf eine rot oder blau umringelte Zahl treffe, das bedeutet dann, ich habe anfangs einfach schlecht gewählt.

Statt Farben zu nehmen könnte man natürlich das Sudoku mehrfach ausdrucken und die einzelenen Varianten durchspielen. Meist reicht aber ein Buntstift.

-Tino, 2007-02-17, Letzter update 2007-04-24