Im folgenden wird das Automatische Lösen beschrieben, das in diesem Programm implementiert ist..
Voraussetzung: Sie haben Startwerte bereitgestellt, eventuell auch schon ein wenig selber probiert und wollen nun die Lösung automatisch berechnen. Als Startwerte müssen Sie nicht notwendigerweise Zahlen eingeben. Ein leeres SUDOKU mit 9 Optionen in jedem Feld reicht auch aus. Allerdings Vorsicht:
Sind gar keine Startwerte gegeben, so liefert der Suchalgorithmus 6.670.903.752.021.072.936.960 (ca. 6,7 Trilliarden oder 6,7 · 10^21) Lösungen. Das wird Ihr Rechner kaum verkraften und dauert auch eine Weile.
Deshalb ist die Möglichkeit geschaffen worden, die Anzahl der zu berechnenden Lösungen zu begrenzen. Werden weniger Lösungen bestimmt, als es Ihre Begrenzung erlaubt würde, dann bedeutet dies, dass es weitere Lösungen nicht gibt.
Die Lösungen werden in einer Reihe von Versionen abgelegt, die eine Nachverfolgung der Entstehung und der Schwere des SUDOKUs gestatten. Diese Versionen können über die Steuerbefehle |<<, <<, >> und >>| angeschaut werden.
Die Steuerbefehle befinden sich in dem Menue VARIANTEN DER AUTOMATISCHEN LÖSUNGEN.
Im einzelnen gibt es die folgenden Standardvarianten:
1 Startwerte: Darstellung der Startwerte, so wie sie eingegeben oder eingelesen wurden.
2 Stand vor automatischer Lösung: Rechnungen, die sie vor dem automatischen Lösen durchgeführt haben, Eingaben, die sie vorher gemacht haben, werden hier dokumentiert. Es dokumentiert den Stand des SUDOKUs vor dem automatischen Lösen, nach Setzungen, Optionen und Farben.
3 Konventioneller Lösungsversuch (Benutzer-Einstellung): Hier wird im Rahmen der Prüfungen, die Sie angeklickt haben, eine Lösung berechnet (ohne Raten). Es wird dargestellt, ob durch die Prüfungen eine weitere Verbesserung erzielt werden konnte oder gar eine Lösung berechnet werden konnte.
Wurde eine Lösung berechnet, so ist es auch die einzige Lösung, da sie auf der Basis immer weiterer Einschränkungen der möglichen Optionen erzielt wurde.
Schwere der SUDOKUs: Die einzelnen Prüfungen sind nicht völlig unabhängig voneinander, trotzdem definieren sie eine unterschiedliche Schwere der SUDOKUs. Leichte SUDOKUs sind auch per Hand sehr schnell gelöst, wenn sie nur die Prüfungen 1..3 (1.Stufe) erfordern. Ein SUDOKU, das unter Heranziehung der Prüfungen der Stufe 1 (Zeilen-, Spalten- und Quadrantenprüfung) bereits lösbar ist, ist als leicht einzustufen.
Deshab gibt es:
4 Konventioneller Lösungsversuch (1. Stufe): Hier wird unabhängig davon, welche Prüfungen der Nutzer herangezogen hat, nur auf Basis der Startwerte alles berechnet, was auf der Basis dieser 3 Prüfungen berechenbar ist (Setzungen und Einschränkung der Optionen).
5 Konventioneller Lösungsversuch (2. Stufe): Hier werden Zeilen-, Spalten- und Quadrantenanzahlauswertung und die Identifikation von Einsiedlern
zusätzlich zu den Prüfungen der Stufe 1 herangezogen und geprüft, of es auf dieser Basis bereits eine Lösung gibt. Stufe 2 definiert nur einen unwesentlich höheren Schwierigkeitsgrad als Stufe 1 alleine. Dabei ist die Identifikation von Einsiedlern eigentlich von Stufe 1 bereits erfasst, allerdings ist sie schneller.
6 Konventioneller Lösungsversuch (3. Stufe): Hier werden die sichere Zeilen- und Spalten-Identifikation hinzugezogen. Dies stellt eine etwas stärkere Prüfung dar als Stufe 2, wird allerdings von aufmerksamen SUDOKU-Lösern ebenfalls schnell bemerkt, stellt also bestenfalls eine mittlere Schwere dar.
7 Konventioneller Lösungsversuch (4. Stufe): Hier werden die Suche von sicheren Teilmengen innerhalb von Zeilen, Spalten und Quadranten zu Stufe 3 hinzugezogen. Diese Suche, insbesondere wenn die Positionen im Quadranten nicht nebeneinanderliegen, ist sehr aufwändig und verlangt eine große Gedächtnisleistung. Daher sind solche SUDOKUs schon als mittelschwer zu bezeichnen.
8 Konventioneller Lösungsversuch (5. Stufe): Hier werden die Suche von Zeilen- oder Spalten-Fischen hinzugezogen. Dies sieht ein normaler SUDOKU-Löser, der sich nicht speziell auf Fische trainiert hat, im allgemeinen nicht. Dies sind die schwersten direkt lösbaren SUDOKUs.
9 und weitere: Hier folgen die SUDOKUs die trotz Einsatz der Prüfungen nicht lösbar sind und Raten einzelner Ziffern erfordern. Eigentlich dürfte hier nur noch eine SUDOKU-Lösung folgen, wenn alle Varianten bis 8 keine Lösung ergeben haben. Bei einem SUDOKU wird vorausgesetzt, dass es eindeutig lösbar ist. Um dies auch nachweisen zu können, wurde die Möglichkeit geschaffen, alle Lösungen zu bestimmen. Folgt also nur eine Lösung unter 9, so ist das SUDOKU eindeutig lösbar. Folgen mehrere, so heißt dies, dass das SUDOKU nicht richtig gestellt wurde, also nicht eindeutig ist.
Abbruch: Wenn ein SUDOKU z.B. bereits in Stufe 3 lösbar ist, erkennbar an dem Hinweis "Konv.Lösungsvers.(3.Stufe)-> Eindeutige Lösung". Klar ist, dass dann mit weiteren Prüfbedingungen erst recht eine Lösung zu bestimmen ist. Dies braucht nicht extra nachgerechnet zu werden. Deshalb würde in diesem Fall nur Variante 6 dokumentiert und dann abgebrochen.
Weitere Abbruchkriterien: Zeigt sich auf irgend einer Stufe, dass ein Widerspruch entsteht, das SUDOKU also gar keine Lösung besitzt, so wird ebenfalls abgebrochen, da der Widerspruch nicht auf allen weiteren Ebenen reproduziert werden muss. Der Hinweis lautet in diesem Fall:
"Konv.Loesungsvers.(3.Stufe)-> Widerspruch"
Sind keine Lösung und auch kein Widerspruch aufgetreten, so wird die Anzahl der Optionen gezählt, die nach den Prüfungen noch übrig bleiben. Ist diese Zahl gegenüber der vorangehenden gesunken, so wird dies durch: "Konv.Loesungsvers.(3.Stufe)-> Verbesserung" dokumentiert. Hat sich die Anzahl der Optionen nicht verändert, so wird dies durch: "Konv.Loesungsvers.(3.Stufe)-> Keine Verbesserung" dargestellt. In diesen Fällen ist nicht auszuschließen, dass weitere Prüfungen noch Verbesserungen liefern, daher wird in diesen Fällen nicht abgebrochen, sondern mit weiteren Prüfungen wie oben beschrieben fortgesetzt.
Falls Sie dieses Feld lieber nicht sehen wollen, nutzen Sie "X" rechts oben, dann wird es unsichtbar und die Kommentarrudimente irritieren Sie nicht weiter. Mit dem darunter liegenden Befehl "Feld für automatische Lösungen anzeigen" können Sie es jederzeit wieder sichtbar machen. Wenn Sie automatisch lösen, erscheint es auf jeden Fall wieder.
Die Anzahl der berechneten Lösungen sollte immer kleiner sein als die Anzahl der Varianten, weil auch die Startwerte und die Situation vor dem automatischen Lösen als Varianten auftreten.
|<< zeigt die erste Variante an.
<< zeigt die vorangehende Variante an.
>> zeigt die nächste Variante an.
>>| zeigt die letzte Variante an. Dies sollte eine Lösung sein, falls überhaupt eine Lösung existiert und das SUDOKU nicht überbestimmt ist.
Da Sie möglicherweise meinen Programmierkünsten nicht trauen, gibt es auch die Befehle "Lösungen unterschiedlich?" und "Lösung erfüllt SUDOKU-Regeln?". Damit können Sie nachprüfen, ob alle vorgelegten Lösungen wirklich unterschiedlich sind und den SUDOKU-Regeln entsprechen. Die vorgelegten Lösungen sollten beides erfüllen.
Sie können die Lösungen auch speichern und wieder einlesen. Die Dateien, die dabei erzeugt werden, sind im Klartext lesbar und sollten ausreichend sein, um Lösungen auch in andere Programme zu übertragen.
Falls Sie eine Lösung wieder ausdünnen wollen, um ein eigenes SUDOKU zu erstellen, nutzen Sie den Befehl "Setzungen als Startwerte". Er sorgt dafür, dass alle Setzungen als Startwerte übernommen werden und alle Parameter, die den Berechnungsprozess beschreiben zurückgesetzt werden. Sie können dann mit "Aktive Zelle löschen" oder der Eingabe "l" jeweils die aktive Zelle löschen oder auch, falls Sie den Haken "Lösche symmetrisch um die Mitte" gesetzt haben, jeweils vier Felder löschen. Einen Zwischenstand können Sie dann im grünen Feld "Speichern von Zwischenwerten" speichern und mit dem automatischen Löser analysieren, wie schwer das so erstellt SUDOKU lösbar ist oder ob es überhaupt noch eindeutig lösbar ist.
Hat man genügend ausgedünnt, so speichert man wieder als Zwischenwert und nutzt den automatischen Löser, um das bisher erreichte zu analysieren. Dabei sollte man den automatischen Löser nicht auf 1 begrenzen, eventuell die 50 stehenlassen, um zu sehen, ob die Lösung noch eindeutig ist. Es muss eine Lösung geben, da das Ausgangs-SUDOKU eine solche darstellt. Gibt es mehr als eine Lösung, so hat man in einigen Bereichen schon zu weit ausgedünnt. Man muss geeignete Setzungen wieder einfügen. Man sollte immer nur Zahlen einfügen, die auch im ursprünglichen SUDOKU standen, um die Lösbarkeit zu sichern.
Diesen Prozess wiederholt man so lange, bis man eine Setzung gefunden hat, die dünn genug ist, so dass das SUDOKU einen hinreichenden Schweregrad hat, die aber auch so dicht ist, dass das SUDOKU nur genau eine Lösung besitzt. Wenn Sie mehrere Lösungen haben, Ihr SUDOKU also zu dünn ist, können Ihnen die geratenen Werte des automatischen Lösers Hinweise geben, wo Sie vielleicht Setzungen vorgeben sollten.
Unter dem Befehlsreiter "Transformation" findet man nun noch Möglichkeiten, die Ziffern oder die Anordnung der Zeilen und Spalten so zu ändern, dass aus dem SUDOKU verschiedene werden, die alle den gleichen prinzipiellen Lösungsweg haben, dieser ist aber wegen der Vertauschungen für den ahnungslosen Anwender nicht erkennbar. Genauere Informationen dazu findet man auf dem entsprechenden Befehlsfeld.
Spiegelt man ein SUDOKU an der Hauptdiagonalen 11..99, die also von links oben, dem Feld in der ersten Zeile und ersten Spalte nach rechts unten, dem Feld in der 9. Zeile und 9. Spalte verläuft, so werden Zeilen zu Spalten und umgekehrt, Quadranten werden wieder zu Quadranten, aber das SUDOKU bleibt ein SUDOKU. Dasselbe gilt, wenn Sie an der Nebendiagonalen 19..91 spiegeln, die von rechts oben, dem Feld in der ersten Zeile und 9. Spalte, nach links unten, dem dem Feld in der 9. Zeile und ersten Spalte, verläuft.
Wenn man z.B. die ersten drei Spalten vertauscht, bestehen sie immer noch aus den Ziffern 1..9 und entsprechen damit den SUDOKU- Regeln. Dieser Spaltentausch hat innerhalb jedes Quadranten die Spalten ebenfalls vertauscht, da diese Vertauschung aber nur innerhalb des Quadranten erfolgte, besteht er immer noch aus den Ziffern 1..9, die jetzt nur spaltenweise anders angeordnet sind. In jeder Zeile sind die ersten drei Ziffern vertauscht, es ist aber weder eine verloren gegangen, noch ist eine hinzugekommen. Folglich sind auch nach der Vertauschung der ersten drei Spalten die SUDOKU-Regeln noch komplett erfüllt, auch nach der Vertauschung handelt es sich noch um ein SUDOKU.
Für die Zeilen gilt das eben dargestellte analog auch. Daher kann man Zeilen oder Spalten jeweils innerhalb der Blöcke 1, 2, 3 oder 4, 5, 6 oder 7, 8, 9 vertauschen ohne die SUDOKU-Regeln zu verletzen. Dies kann man beliebig oft machen, man erhält jedesmal wieder ein SUDOKU.
Die SUDOKU-Eigenschaften bleiben ebenfalls erhalten, wenn Sie die Ziffern permutieren, also z.B. jede 9 durch eine 1 und gleichzeitig jede 1 durch eine 9 ersetzen. Dies ist die dritte Transformation, die Ihnen angeboten wird.
Darstellung der Transformationen
Wie in der Kombinatorik üblich, werden die Transformationen durch Zyklen dargestellt. Die hier angewandten Transformationen sind alle
Permutationen, also Zuordnungen, die eine kleinen Anzahl von Ziffern in eindeutigerweise aufeinander abbilden, so dass jede Ziffer genau
einmal Urbild und genau einmal Bild ist. Dies tut man in der Kombinatorik, indem man Zyklen, das sind Ziffernfolgen, schreibt:
123 bedeutet, dass der 1 die 2, der 2 die 3 und der 3 die 1 zugeordnet wird.
Sind die ersten 3 Spalten gemeint, und lautet der Zyklus 12, so bedeutet dies, dass die Spalten 1 und 2 vertauscht werden und die Spalte 3
bleibt, wo sie ist. Um die Sache zu vereinfachen, können Sie den Zyklus 12 stehenlassen, wenn Sie die Spalten 7..9 vertauschen wollen, die erste
zu vertauschende Spalte ist dann Spalte 7, die zweite Spalte 8 und die dritte Spalte, die nicht bewegt wird, ist Spalte 9. Falls Sie versuchen, unter
Zyklus Ziffern außer 1, 2, 3 einzugeben, lässt das Programm das nicht zu.
Bei der Permutation einer größeren Anzahl von Ziffern kann es vorkommen, dass es mehrere Zyklen gibt. So bedeutet der Zyklus 123456789, dass
die Ziffer 1 durch 2, die Ziffer 2 durch 3 usw. und schließlich die Ziffer 8 durch 9 und die Ziffer 9 durch 1 ersetzt wird. Es kann aber sein, dass Sie
die Ziffern 1 durch 2, die Ziffer 2 durch 3, die Ziffer 3 durch 4 und die Ziffer 4 durch 1 ersetzen wollen, die Ziffer 5 soll nicht bewegt werden und
die Ziffern 6 und 7 und 8 und 9 sollen jeweils vertauscht werden. Dies stellt man durch drei Zyklen dar, die in unserer Darstellungsweise durch
Kommata getrennt werden, in der Mathematik benutzt man dafür Klammern. Die Zyklen lauten 1234,67,89. Das Eingabefeld unter "Permutation
der Ziffern" erlaubt nur die Eingabe der Ziffern 1..9 und des Kommas. Um sicher zu gehen, dass das Programm auch das macht, was Sie wollen,
gibt es das Häkchen "Permutation anzeigen", das Ihnen die entstandene Zuordnung noch einmal zeigt.
Haben Sie etwas falsch gemacht, so gibt es zu jeder Permutation auch eine solche, die sie wieder rückgängig macht. In unserem Beispiel 1234,67,89 ist es 1432,67,89. Wenn Sie vor dem Permutieren zwischenspeichern, können Sie sich das ursprüngliche SUDOKU auch ohne Berechnung der inversen Permutation zurückholen.
Sie können die gespeicherte Datei in jedem Editor lesen. Die Ziffernfolgen sind kommentiert, so dass Sie die Zwischenwerte auch in ein anderes Programm übertragen können. Die Speicherung der Zwischenwerte erfolgt mit allen weiteren relevanten Parametern einschließlich der Farbe.
Falls Sie dies bei der Weiterverarbeitung eines Zwischenwertes stört, weil Ihnen der Zwischenwert eher als Startwert weiterer Überlegungen dienen soll, dann wählen Sie im Befehlsregister LÖSEN den Befehl "Setzungen als Startwerte". Dann sind Sie die Parameter des Verlaufs losgeworden und alle Setzungen erscheinen in schwarzer Schrift als Startwerte. Nach dem Befehl "Setzungen als Startwerte" können Sie dann mit "Aktive Zelle löschen" oder der Eingabe "l" jeweils die aktive Zelle löschen oder auch, falls Sie den Haken "Lösche symmetrisch um die Mitte" gesetzt haben, jeweils vier Felder löschen. Einen erneuten Zwischenstand können Sie dann im grünen Feld "Speichern von Zwischenwerten" speichern und mit dem automatischen Löser analysieren, wie schwer das so erstellt SUDOKU lösbar ist oder ob es überhaupt noch eindeutig lösbar ist. Durch Hinzufügen oder Löschen von Setzungen können Sie dann ein eigenes SUDOKU erzeugen. Prüfen Sie aber immer nach, ob es noch eindeutig lösbar ist.