RZ-SUDOKU-Entzauberer Version 4

Die Hilfedateien als Programmbeschreibung


Rechts oben mit dem Schalter HILFE finden Sie einen Überblick, der die primären Funktionen beschreibt:


Informationen zu RZ-SUDOKU-Entzauberer

Dieses Programm wurde von Robert Zobel geschrieben, um für ein SUDOKU einen schnellen Überblick bereit zu stellen.

Der Benutzer hat die Möglichkeit mit "Neu" ein eingegebenes SUDOKU zu löschen und ein leeres Feld zu erzeugen. Er wird ernst genommen. Keine Frage quält ihn, ob er das auch wirklich wolle. Keine Rückkehr zum alten Status ist möglich.

Dazu gibt es "Daten speichern", mit dem der Benutzer einen erreichten SUDOKU-Stand abspeichern kann, den er dann mit "Öffnen" wieder einstellen kann.

Es gibt keine Druck-Funktion, aber die Funktion "Bild speichern". Mit dieser Funktion erzeugt man eine Pixel-Datei, die man in jedem Bildverarbeitungprogramm auf den Drucker bringen kann.

"Daten speichern" macht aus den eingegebenen Werten eine ASCII-Datei, bei der unbekannte Werte Nullen sind.

Beispiel einer solchen Datei:
702680000
030000407
000007000
906000700
000703000
005000108
000900000
408000090
000041302
Ende der Beispieldatei.

Mit "Öffnen" kann man eine solche Datei wieder einlesen oder auch eine selbst erstellt Datei einlesen. Eine selbst erstellte Datei muss in neun Zeilen je 9 Ziffern aufweisen. Weitere Folgezeilen sind ohne Belang. Nichtnumerischer Text wird als Ziffer 0 interpretiert. Ebenso wird alles ignoriert, was auf das 9. Zeichen folgt. Fehlende Zeichen oder Zeilen werden komplett als 0 interpretiert. Wenn Sie mit "Daten speichern" arbeiten, werden tatsächlich nur die bis dahin erfolgten Setzungen gespeichert. Die weiteren Informationen wie verbliebene Optionen usw. werden nicht gespeichert. Dies leistet das Speichern von Zwischenwerten und kann in der Hilfe zu diesem Thema genauer studiert werden.

"Ende" ist Ende ohne WENN und ABER und ohne enttäuschte Rückfragen des Programmes.

Die 9*9-Matrix liefert das Feld, auf dem das SUDOKU gespielt werden kann. Im Hintergrung jedes Feldes sind die Ziffern 1..9. Sie verschwinden, wenn eine Zahl eingetragen wird. Ansonsten beschreiben sie unter den eingestellten Prüfbedingungen die Anzahl der noch möglichen Werte.

Eingabe in das SUDOKU-Feld: Zunächst wird auf ein Feld geklickt, damit es zur aktiven Zelle wird. Man erkennt die aktive Zelle am roten Rahmen. Dann gibt man über die Tastatur die gewünsche Zahl ein. Generell kann man nur Ziffern von 1 bis 9 eingeben. Ist Eingabe-Überprüfung" markiert, so kann man nur Zahlen eingeben, die in der Zeile, in der Spalte und in dem Quadranten der aktiven Zelle nicht vorkommen. Dies entspricht den SUDOKU-Regeln.

Achtung, hat man ohne Eingabe-Überprüfung zwei 3-en eingegeben, so muss man sie auch wieder manuell entfernen.

Interessanter sind die Prüfungen, die das Programm anstellt. Dadurch werden die kleinen Ziffern im Hintergrund beeinflusst. Sie verschwinden, wenn an der Stelle eine solche Zahl nicht möglich ist. Nicht möglich ist relativ zu den angeklickten Prüfungen zu verstehen.

Die Anzahl der freien Optionen wird oben links angegeben. Sie ist ein Maß für die Nähe zur Lösung, die man bereits erreicht hat. Mit dem Befehl KONSEQUENZ kann man noch weitere Informationen erhalten.

Mit der Eingabe a wandert die aktive Zelle nach links, mit der Eingabe w nach oben und mit s und d nach rechts, mit y nach unten. Mit l (der kleine Buchstabe L) löscht man den Inhalt der aktiven Zelle, falls es für diese Zelle eine Setzung gibt. Mit "Aktive Zelle löschen" kann man ebenfalls die Eingabe in der aktiven Zelle löschen. Es wird jeweils die aktive Zelle gelöscht. Ist das Häkchen "Lösche symmetrisch um die Mitte" gesetzt, so wird mit dem Feld (3,2) auch das Feld (3,7), das Feld (6,3) und (6,7) gelöscht. Dies kann beim Erzeugen eigener SUDOKUs hilfreich sein. Mehr dazu unter "Eigenes SUDOKU".

Achtung: Es gibt keinen Weg zurück, man muss die gelöschten Werte manuell wieder eingeben, falls man nicht vor dem Löschen den Stand im Zwischenspeicher gesichert hat.

Wollen Sie eine Prüfung unter Berücksichtigung der eingegebenen Werte durchführen, klicken Sie "Neue Prüfung". Dann werden alle bisherigen Prüfungen zurückgesetzt und neu begonnen. Jede Prüfung wird nur einmal durchgeführt. Daher kann es Sinn haben, die Prüfung noch einmal durchzuführen. Dies leistet "Prüfung fortsetzen".

Da es mühsam ist, alle eindeutig bestimmten Werte manuell einzugeben, gibt es noch die Taste "Alle eindeutig bestimmten Werte einsetzen".

Wenn Sie neue Werte einlesen, finden Sie diesen Stand in dem kleinen Menue rechts mit der Überschrift "Startwerte". Sie können mit "->" einen Zwischenstand im rechten Feld speichern und mit "<-" wieder holen. Falls Sie "Automatisch speichern" gesetzt haben, sehen Sie für jede neue Eingabe ein Anzeige im grünen Feld. Dadurch werden aber sehr viele Zwischenstände gespeichert.

Ein automatischer Löser existiert und wird in dem Feld "Automatisches Lösen" unter "?" beschrieben.

Die Art der Prüfungen wird links unter "Pr ?" genauer erläutert, die Bedeutung der Farben unter "Fa ?".




Da es im vorangehenden Text schon angekündigt wurde, nun die Beschreibung der Prüfungen, die das Programm ausführen kann:

Die Prüfbedingungen

Im folgenden werden die Prüfbedingungen beschrieben. Es werden nur die Prüfbedingungen angewandt, die auch durch ein Häkchen ausgewählt sind. Jede Prüfbedingung kommt im allgemeinen dreifach daher, weil sie innerhalb einer Zeile, einer Spalte oder eines Quadranten angewandt werden kann.

Im folgenden werden Zeilen von oben nach unten, Spalten von links nach rechts und Quadranten erst von links nach rechts und dann von oben nach unten gezählt. Oben links ist also der erste, oben in der Mitte der zweite Quadrant.

Zeilen-, Spalten- und Quadrantenprüfung:
Taucht eine Ziffer innerhalb einer Zeile, Spalte oder eines Quadranten auf, so kann sie dort nicht noch einmal vorkommen. Ist in der siebten Zeile im Feld 4 eine 3, so kann in Zeile 7, in Spalte 4 und im achten Quadranten keine 3 mehr auftauchen, sie ist als Option also zu streichen. Die Regeln des SUDOKU wollen es so.

Zeilen-, Spalten- und Quadrantenanzahl-Auswertung:
Hier haben wir den umgekehrten Blickwinkel. Wir wissen, dass in jeder Zeile eine 3 vorkommen muss. Können wir in einer Zeile nur eine mögliche Position für die 3 ausmachen, so muss sie dort auch stehen und alle anderen Möglichkeiten in dieser Zeile entfallen. Handelt es sich wieder um die siebten Zeile, in der wir für alle Felder mit Ausnahme von Feld 4 ausschließen können, dass dort eine 3 steht, so muss die 3 dort auch stehen, denn irgenwo in der Zeile muss sie ja vorkommen. Üblicherweise schaut man eine Zeile an und prüft alle leeren Felder der Zeile, ob etwa in der Spalte oder im Quadranten dieses leeren Feldes schon eine 3 steht.

Sichere Zeilen- und Spaltenidentifikation:
Manchmal kann man in einem Quadranten erkennen, in welcher Zeile des Quadranten die Zahl stehen muss. Wenn etwa alle Felder des achten Quadranten, soweit sie in Zeile acht und neun stehen, belegt sind, aber keine 3 dabei ist, so muss die 3 in den Feldern des achten Quadranten, die in Zeile sieben sind, auftauchen. Damit kann die drei in Zeile sieben nur in Spalte vier, fünf oder sechs vorkommen, aus allen anderen Feldern der Zeile acht ist sie als Option zu streichen.

Sichere Teilmengen von Zeilen, Spalten oder Quadranten:
Die obigen Kriterien prüft man mit vertretbarem Aufwand auch bei einer manuellen Lösung eines SUDOKU. Die sicheren Teilmengen sind erst bei intensiver Beschäftigung mit dem SUDOKU zu erkennen.
Die Idee ist relativ einfach: Nehmen wir einmal an, wir erkennen, dass in Zeile sieben unseres SUDOKUs die Zahlen 3, 5 und 8 nur in den Spalten vier, sechs und neun vorkommen können. Dann haben wir für die drei Ziffern genau drei Positionen, wo sie stehen können. Da sie in Zeile sieben vorkommen müssen, werden sie dort auch auftreten, wir wissen nur noch nicht, wo genau. Also können wir ausschließen, dass die drei Ziffern in irgend einer anderen Position als Spalte vier, sechs und neun vorkommen. Dort können wir die Optionen 3, 5, 8 also streichen. Umgekehrt können wir im Inneren, in den Feldern vier, sechs und neun ausschließen, dass dort noch andere Ziffern auftreten, auch diese Optionen können wir also streichen.

Zeilen- und Spalten-Fische:
Hintergrundinformationen zu den Fischen findet man im Internet unter den Bezeichnungen Kreuzflügler (X-wing), Schwertfisch (Swordfish) oder Qualle (Jellyfish). Die Grundidee ist die folgende: In n Zeilen findet man, dass in n Positionen (Spalten) nur die Zahlen x1, ..., xn stehen können. Da jede dieser n Zahlen in jeder der n Zeilen vorkommen muss und dafür nur n Positionen zur Verfügung hat, brauchen die Zahlen x1, ..., xn auch diese n Positionen. Damit tauchen sie aber auch in den n Spalten nur an den Positionen auf, die durch die n Zeilen bestimmt sind. Dies bedeutet, dass sie in den n Spalten außerhalb der n Zeilen nicht vorkommen können, dort also als Option gestrichen werden können.
Wikipedia beschreibt in seinem Artikel über SUDOKUs Beispiele, die Sie mit diesem Programm nachrechnen können. Mit Hilfe der Anzeige über das Häkchen "Verbesserungen anzeigen" können Sie den Fisch sichtbar machen.

Für die letzten drei Prüfungen, "Sichere Zeilen- und Spaltenidentifikation", "Sichere Teilmengen von Zeilen, Spalten oder Quadranten" und Zeilen- und Spalten-Fische gibt es auch die Möglichkeit, gefundene Identifikationen oder Teilmengen anzuzeigen. Dazu ist das Häkchen "Verbesserungen anzeigen" zu setzen. Die fraglichen Felder werden durch Umrandungen gekennzeichnet und ein erklärender Text wir ausgegeben. Für die ersten beiden Varianten wurde dieses Hilfsmittel nicht programmiert, weil es nur zu ermüdendem Quittierungen des Benutzers führt und der Erkenntnisgewinn minimal ist.




Die Farben der SUDOKU-Ziffern

Die großen SUDOKU-Ziffern können durch Eingabe des Benutzers, durch den Befehl "Alle eindeutig bestimmten Werte einsetzen" oder im Zuge des automatischen Lösens oder durch Rückspeicherung aus dem grünen Feld, das als Zwischenspeicher dient, entstanden sein. Durch eine geeignete Farbgebung soll dies transparent bleiben.

clBlack
Die Startwerte werden schwarz eingegeben. Startwerte sind die Werte, die über die Funktion "Öffnen" eingelesen worden sind, bzw. die Werte, die nach Ausführen von "Neu" oder nach Programmstart bis zum Befehl "Ende Eingabe Startwerte" eingegeben worden sind.

clMaroon
Die Werte, die der Benutzer nach Eingabe der Startwerte zusätzlich eingibt, weil er sie selbst bestimmt hat, werden in einem Braunton dargestellt. Alle Benutzereingaben nach "Ende Eingabe Startwerte" werden so dargestellt.

clGreen
Die Werte, die der Computer berechnet hat und über den Schalter "Alle eindeutig bestimmten Werte einsetzen" einsetzt, werden in grün dargestellt.

clRed
Beim automatischen Lösen mit Probieren wird das Programm, wenn die Berechnungen entsprechend der Prüfbedingungen nicht ausreichen, einzelne Werte raten, um daraus eine konsistente Lösung zu berechnen. Diese geratenen Werte werden in rot dargestellt.

clAqua
Die Werte, die beim automatischen Lösen durch Rechnung bestimmt worden sind, werden in einem hellen Blau dargestellt.

Die Farbverteilung wird im Zwischenspeicher (grüne Fläche rechts vom SUDOKU-Feld) dokumentiert und erscheint erneut, wenn aus dem Zwischenspeicher zurückgeladen wird.

Als Beispiel dazu eine SUDOKU, in dem in schwarz die Startwerte, in dunkelrot (mittlere Spalte, die Ziffern 2 und 5) vom Anwender eingegebene Werte und in grün Werte eingetragen sind, die als eindeutig bestimmte Werte vom Programm automatisch gesetzt wurden. In diesem Fall wurden nur die einfachsten Prüfungen gewählt, daher gibt es noch so viele Optionen in unbesetzten Feldern,169 Optionen für 48 freie Felder, im Schnitt also 3,5 je unbesetztem Feld.


Wählt man alle Prüfungen mit Ausnahme der Fische, so bleiben noch 117 freie Optionen bei 41 noch zu besetzenden Feldern, 2,9 je freiem Feld, also nur ein beschränkter Fortschritt.


Erst die Hinzunahme der Fische löst das SUDOKU, wie das nächste Bild zeigt:


Ein Klick auf "Alle eindeutig bestimmten Werte einsetzen" und die Lösung steht explizit da.

Wählt man das automatische Lösen, so erhält man das vorliegende Ergebnis ebenfalls, da der automatische Löser versucht, erst auf Basis der ersten drei, dann der ersten sieben, der ersten neun, der ersten zwölf und schließlich aller vierzehn Prüfungen zu lösen. Jeder Fehlschlag und die Lösung selbst wird dokumentiert. Damit bekommt man zusätzlich zur Lösung eine Schwere-Information über das SUDOKU. Wenn alle Prüfungen nicht ausreichen für eine Lösung, beginnt der Löser ein systematisches Raten und ist dadurch auch in der Lage, bei unterbestimmten SUDOKUs alle Lösungen anzugeben.



SUDOKU-Ankündigung
Informationen zu Version 4 - Seite 2
Hauptseite
Anregungen, Fragen, Hinweise an: robert.zobel@predige-das-wort.de
Wegweiser durch die Webseite