Information Technology Reference
In-Depth Information
Die wichtigste Lösungsstrategie ist eine Regel, die wir als „hypothetisch-deduktiv“ bezeich-
nen; Crook nennt eine ähnliche Regel „Hypothese samt Backtracking“ (vgl. auch Delahaye
2006). Gemeint ist damit, dass das Programm bei der Entscheidung, welche Zahl in eine leere
Zelle gesetzt werden soll, zunächst die Umgebungsbedingungen prüft. Gibt es nur eine mögli-
che Lösung, wird die entsprechende Zahl eingesetzt. Sind mehrere Lösungen möglich, wird
eine Lösung zufällig ausgewählt; dieser Schritt wird in einer Datei gespeichert. Der ZA prüft
dann die jeweils nächste Zelle und verfährt entsprechend. Falls sich bei einem der nächsten
Schritte herausstellt, dass bei einer leeren Zelle keine Lösung möglich ist, geht der ZA zu dem
Zustand zurück, bei dem die letzte hypothetische Auswahl vorgenommen wurde und versucht
es mit einer anderen möglichen Lösung. Führt auch diese nicht zum Erfolg, werden die anderen
Möglichkeiten überprüft. Falls keine Möglichkeit zu einer Lösung führt, geht der ZA zu der
vorletzten hypothetischen Auswahl und so fort.
Wir nennen diese Strategie hypothetisch-deduktiv, weil der ZA gewissermaßen Hypothesen
über sein mögliches Procedere aufstellt und prüft, welche Konsequenzen sich aus einer Ent-
scheidung ergeben (Deduktion). Auf diese Weise findet der ZA entweder eine Lösung, unab-
hängig davon, ob es auch noch andere gibt, oder der ZA erkennt das spezielle Sudoku-Rätsel
als unlösbar. Als Beispiel zeigen wir ein Rätsel, das aus jeweils 4
*
4 Feldern besteht und das
den Anfangszustand des ZA darstellt (Bild 2-27); das nächste Bild zeigt einen „Zwischenzu-
stand“ (2-28), in dem der ZA schon einige Lösungen gefunden hat, aber von der Endlösung,
gewissermaßen dem Lösungsattraktor, noch deutlich entfernt ist; Bild 2-29 schließlich zeigt
den Endzustand, in dem eine Endlösung gefunden worden ist.
Bild 2-27
Startzustand des ZA
Search WWH ::
Custom Search