Kapitel 3: Solver konfigurieren

Inhaltsverzeichnis

L�sungsstrategie
L�sungstechniken (de-)aktivieren
Reihenfolge der L�sungstechniken �ndern
Zweideutigkeiten und Beispiele
Fortschrittsma�
- Ausdr�cke und Definitionen
- L�sen bis
Suche nach Hintert�ren
Optionen f�r L�sungstechniken

L�sungsstrategie

Der interne Solver von HoDoKu verwendet dieselbe prinzipielle L�sungsstrategie wie die Solver der meisten anderen Sudokuprogramme auch. F�r die verf�gbaren L�sungstechniken ist eine Reihenfolge definiert. Der Solver probiert jetzt eine Technik nach der anderen in genau dieser Reihenfolge aus. Sobald er einen m�glichen L�sungsschritt findet, f�hrt er ihn aus und beginnt die Suche wieder mit der ersten Technik.

Die Reihung der Techniken basiert auf ihrem Schwierigkeitsgrad (leichtere Techniken vor schwereren). Wie schwer eine Technik wirklich ist, ist nat�rlich oft genug Ansichtssache, daher bietet HoDoKu die M�glichkeit, die Reihenfolge der L�sungstechniken nach Belieben zu �ndern (siehe unten).

Die Folge dieser Strategie ist, dass der Solver niemals eine komplizierte Technik verwendet, wenn noch eine einfachere verf�gbar ist. Das bedeutet wiederum, dass er nur sehr selten die k�rzest m�gliche L�sung findet. Im Normalfall wird die L�sung mit den einfachsten Techniken gefunden, unabh�ngig davon, wie oft diese Techniken angewendet werden m�ssen.

Die Standardreihenfolge kann unter "Bearbeiten|Einstellungen|Solver" nach Dr�cken von "Zur�cksetzen" eingesehen werden. Mit Version 2.0 von HoDoKu listet dieser Dialog 91 verschiedene Techniken, von denen einige allerdings zur selben Familie geh�ren (z.B. allein 42 verschiedene Fish-Varianten). Andere Techniken haben nur einen Eintrag in der Liste, k�nnen aber unterschiedliche L�sungsschritte produzieren (der Eintrag "Nice Loops/AIC" kann z.B. "Discontinuous Nice Loops", "Continuous Nice Loops" und "AICs" erzeugen).

L�sungstechniken (de-)aktivieren

Screenshot: Standard order of solver steps

L�sungstechniken k�nnen aktiviert oder deaktiviert werden. Eine deaktivierte Technik wird vom Solver nicht angewendet.

Einige Techniken ben�tigen f�r die Suche sehr viel Zeit und sind daher standardm��ig deaktiviert (z.B. alle gr��eren Fisch-Typen). Werden solche Techniken aktiviert, kann die Zeit, die der Solver zum L�sen eines Sudokus ben�tigt, sehr stark ansteigen.

Techniken, die dem Spieler nicht besonders liegen, k�nnen nat�rlich ebenso deaktiviert werden (sie werden dann auch vom Hinweis-System nicht angeboten). Eine Technik ein- oder auszuschalten ben�tigt zwei Arbeitsschritte: Zun�chst muss die Technik angeklickt werden, damit sie hervorgehoben wird. HoDoKu f�llt die Eingabeelemente unter "Eigenschaften L�sungschritt" mit den Daten der Technik. Sobald eine Technik hervorgehoben ist, schalten weitere Klicks auf die Zeile die Checkbox ein bzw. aus.

Alle �nderungen, die in diesem Dialog durchgef�hrt werden, werden bei Programmende automatisch in eine Konfigurationsdatei gespeichert (siehe Konfigurationen und Sudokus speichern/laden).

Klick auf den "Baum"-Knopf oberhalb der Liste mit den L�sungstechniken schaltet die Anzeige in den Kategorie-Modus. Techniken werden als Baum nach Kategorien gruppiert angezeigt. Das macht es einfach, ganze Gruppen von Techniken mit einem Klick ein- oder auszuschalten (z.B. alle Chains oder alle Mutant Fische). Die Reihenfolge der Techniken (siehe unten) kann in der Baumansicht nicht ver�ndert werden.

Reihenfolge der L�sungstechniken �ndern

Um die Reihenfolge der L�sungstechniken zu �ndern muss ebenfalls die entsprechende Technik angeklickt werden. Sobald sie hervorgehoben wurde, k�nnen die Kn�pfe "Nach oben" und "Nach unten" dazu verwendet werden die Position der Technik in der Liste zu ver�ndern.

Achtung: Wird die Reihenfolge der L�sungstechniken ge�ndert, kann das zu einer v�llig anderen L�sung f�hren und damit auch die Bewertung des Sudokus ver�ndern (siehe Bewertung und Schwierigkeitsstufen).

Andererseits wirken sich �nderungen der L�sungsreihenfolge nicht nur auf den Solver, sondern auch auf das Hinweis-System aus. Techniken, die dem Spieler besonders liegen, sollten daher in der Liste weiter nach oben verschoben werden. Unbeliebte Techniken sollten besser deaktiviert werden. Soll eine Technik nur als letzter Strohhalm zum Einsatz kommen, sollte sie ans Ende der Liste verschoben werden.

Zweideutigkeiten und Beispiele

Viele Techniken existieren unter mehr als einem Namen. Ein Skyscraper beispielsweise ist sowohl ein Turbot Fish als auch eine X-Chain. Au�erdem kann er als Kombination zweier Sashimi X-Wings gesehen werden. Einige Empty Rectangles k�nnen ebenso Turbot Fishes oder Finned Mutant X-Wings sein.

Durch Ver�ndern der Reihenfolge bzw. (de-)aktivieren von L�sungsschritten kann daher erreicht werden, dass bestimmte Schritte nur unter einem bestimmten Namen gelistet werden. Als Beispiel sollen die folgenden Techniken in ihrer Standardreihenfolge dienen:

2-String-Kite
Skyscraper
Turbot Fish
Empty Rectangle

Empty Rectangles werden nur angezeigt, wenn in der Box, die das ER enth�lt, mindestens drei Kandidaten gesetzt sind. ERs mit nur zwei Kandidaten k�nnen �ber eine Option aktiviert werden. Da solche ERs aber immer auch Turbot Fishes sind und Turbot Fish vor Empty Rectangle kommt, werden diese Schritte immer als Turbot Fish gelistet und die oben genannte Option hat scheinbar keinerlei Effekt. Wenn man wirklich ERs mit zwei Kandidaten als ERs gelistet sehen will, muss entweder Empty Rectangle vor Turbot Fish geschoben werden oder Turbot Fish muss ganz deaktiviert werden. Ebenso bewirkt das Verschieben von Turbot Fish vor 2-String-Kite oder Skyscraper, dass diese Techniken nicht mehr vorkommen, da alle m�glichen Eliminierungen bereits vom Turbot Fish Code erkannt werden.

Fortschrittsma�

Ausdr�cke und Definitionen

L�sungsschritte k�nnen danach beurteilt werden, wie weit sie die L�sung des Sudokus voranbringen. Das wird als "Fortschrittsma�" des L�sungsschritts bezeichnet. Um dieses Fortschrittsma� zu berechnen, wird das Sudoku mit einem konfigurierbaren Set an Techniken gel�st. Der Screenshot zeigt den Konfigurationsdialog f�r diese Techniken. Techniken k�nnen nur gew�hlt werden, wenn ihr Schwierigkeitsgrad maximal "Schwer" ist. Muss unbedingt eine "Unfaire" oder "Extreme" Technik gew�hlt werden, muss zuerst ihr Schwierigkeitsgrad angepasst werden.

In der Listenansicht kann auch die Reihenfolge der Techniken unabh�ngig von der Reihenfolge im normalen Solver ge�ndert werden.

Um die Konfiguration weiter zu vereinfachen stehen mehrere Standardeinstellungen zur Verf�gung:

Default: Singles, Intersections und Subsets
Mittel + Schwer: Alle Schritte, die als "Mittel" oder "Schwer" eingestuft sind
Mittel: Alle Schritte, die als "Mittel" eingestuft sind
SSTS (Simple Sudoku Technique Set): Full House, Naked Single, Hidden Single, Locked Pair, Naked Pair, Locked Candidates, Locked Triple, Naked Triple, Naked Quadruple, Hidden Pair, X-Wing, Swordfish, Simple Colors, Multi Colors, Hidden Triple, XY-Wing, Hidden Quadruple (in der oben angegebenen Reihenfolge). Diese Auswahl an Techniken wird in vielen Sudoku-Foren verwendet, um ein Sudoku bis zu einem "interessanten" Zustand zu l�sen

Das Fortschrittsma� f�r einen L�sungsschritt besteht aus drei unabh�ngigen Werten:

Anzahl direkter Singles: Anzahl an Singles, die verf�gbar sind, nachdem der Schritt ausgef�hrt wurde, ohne dass andere Schritte notwendig sind
Anzahl Singles: Gesamtanzahl an Singles nach Anwendung des Schrittes und unter Verwendung des gesamten Sets an Techniken f�r das Fortschrittsma�
Score: Der Score aller Schritte (nur Fortschrittsma�) nach Anwendung des L�sungsschritts. Kann das Sudoku nicht gel�st werden, wird der Score f�r "Gebe auf" nicht mitgerechnet

L�sen bis

Die Einstellungen in diesem Dialog werden auch von der "L�sen bis"-Funktion im Hinweis-Bereich verwendet. Wird dieser Knopf gedr�ckt, wird die normale L�sungsstrategie angewendet. Wenn die jeweils n�chste gefundene Technik als Fortschrittsma�-Technik definiert ist, wird der L�sungsschritt automatisch angewendet und der n�chste Schritt wird gesucht. Der Prozess stoppt, sobald die erste Technik gefunden wurde, die hier nicht gew�hlt ist.

Suche nach Hintert�ren

Die meisten Sudokus, auch ganz schwere, haben eine oder mehrere Hintert�ren: Eine Hintert�r ist eine Zelle oder eine Kombination aus Zellen, die, wenn gesetzt, die L�sung auf Singles reduziert. Die meisten Sudokus haben Hintert�ren, die nur aus einer einzigen Zelle bestehen. Extrem schwere Sudokus ben�tigen zwei Zellen um leicht zu werden. Das ber�hmte Easter Monster (von JPF im April 2007 im New Sudoku Player's Forum gepostet) ben�tigt sogar drei bestimmte Zellen, bevor es sich mit Singles l�sen l�sst.

HoDoKu kann verschiedene Typen von Hintert�ren berechnen: Hintert�ren f�r Zellen (sowohl mit Singles als auch mit den L�sungsschritten f�r das Fortschrittsma�) und Hintert�ren f�r Kandidaten oder Kombinationen von Kandidaten.

Bei der Suche werden zun�chst Einzelzellen getestet. K�nnen keine Hintert�ren gefunden werden, wird die Suche mit Zellpaaren und wenn n�tig auch mit Dreierkombinationen fortgesetzt. Diese Suche kann unter Umst�nden sehr lange dauern.

Wenn nach Kandidaten-Hintert�ren gesucht wird, kann die Suchtiefe mit einer Combobox eingestellt werden. Wie bei den Zellen stoppt die Suche, sobald Hintert�ren gefunden wurden. Da es normalerweise wesentlich mehr Kandidaten als ungel�ste Zellen gibt, bedeutet eine Suchtiefe von 3, dass HoDoKu eine enorme Anzahl an Kandidatenkombinationen probieren muss, was naturgem�� auch sehr lange dauert.

Optionen f�r L�sungstechniken

Jede L�sungstechnik ist einem Schwierigkeitsgrad zugeordnet ("Level") und hat einen Score. Der Sinn dieser Eigenschaften wird detailliert in Kapitel 4: Bewertung und Schwierigkeitsstufen erkl�rt. Zus�tzlich kann das Verhalten einiger Techniken mit den Optionen in "Bearbeiten|Einstellungen|L�sungsschritte" ge�ndert werden:

Fische allgemein (Optionen beeinflussen alle Fisch-Typen au�er Kraken Fish):

Maximale Anzahl Fins: Maximale Anzahl an Fins ("Flossen"), die bei der Suche nach Finned Fish zugelassen ist. Obwohl eine gr��ere Anzahl an Flossen m�glich ist, ist es sehr unwahrscheinlich, dass ein solcher Fisch Eliminierungen bewirken kann (bei einem Finned Fish muss der eliminierte Kandidat alle Flossen sehen). Eine Erh�hung dieses Wertes bewirkt eine drastische Vergr��erung der Laufzeit der Fischsuche.
Maximale Anzahl Endo-Fins: Maximale erlaubte Anzahl an Endo-Fins bei der Fischsuche. Eine gro�e Anzahl an Endo-Fins ben�tigt speziell bei der Suche nach gro�en Mutant Fischen extrem lange Rechenzeiten ohne deutlich bessere Ergebnisse zu erzielen.
Anzeigetyp: "Normal" zeigt Fische wie in den Versionen vor 2.0 an. "Zahlen" und "Zellen" geben zus�tzliche Informationen �ber die Architektur des Fisches.
Templates pr�fen: Templates sind eine M�glichkeit zu pr�fen, ob Techniken, die sich nur auf eine Ziffer beziehen, prinzipiell noch Eliminierungen bewirken k�nnen. Achtung: Ein negativer Template-Check garantiert, dass kein in HoDoKu implementierter Fisch-Typ (au�er Kraken) eine Eliminierung liefern kann. Das Gegenteil ist allerdings nicht notwendigerweise wahr.
Nur ein Fisch pro Eliminierung: Wenn gew�hlt wird f�r jede m�gliche Kombination an Eliminierungen jeweils nur der kleinste verf�gbare Fisch angezeigt.

Kraken Fische:

Typ: Der Typ des im Kraken Fisch enthaltenen Fisches (Basic, Basic und Franken oder alle Fischtypen).
Maximale Anzahl Fins: Maximale Anzahl an Fins f�r den Kraken Fisch.
Max. Anzahl Endo-Fins: Maximale Anzahl an Endo-Fins f�r den Kraken Fisch.
Maximale Gr��e: Maximale Anzahl an Base/Cover-Sets f�r den Fisch.

Chains allgemein (Optionen beeinflussen X-Chains, XY-Chains und Remote Pairs):

Maximale Chainl�nge: Maximale Anzahl an Links in einer Chain (Achtung: eine XY-Chain mit f�nf Zellen hat neun Links).
Maximale Nice-Loop-L�nge: Diese Option hat keinerlei Auswirkungen mehr und wird in sp�teren Versionen von HoDoKu entfernt werden.

Tabling allgemein (Optionen beeinflussen Nice Loops, AICs, Forcing Chains/Nets und Kraken Fish):

Anzahl Eintr�ge: maximale Anzahl an m�glichen Auswirkungen pro Voraussetzung. Eine niedrige Zahl in diesem Feld bewirkt, dass weniger Chains gefunden werden k�nnen. Eine gro�e Zahl vergr��ert auch HoDoKus Speicherbedarf und verlangsamt die Ausf�hrung des Solvers.
Netztiefe: Legt fest, wie weit bei einer Netzsuche in die Zukunft geschaut werden soll. Je gr��er diese Nummer ist, desto komplizierter werden auch die gefundenen Forcing Nets und die Ausf�hrungszeit steigt (das f�hrt allerdings nicht notwendigerweise zu mehr Eliminierungen).
Nur eine Chain pro Eliminierung: Wenn gew�hlt, werden Chains nur dann eingeschrieben, wenn f�r diese Eliminierung noch keine Chain existiert oder wenn die existierende Chain l�nger ist als die neue.
ALS in Chains erlauben: ALS als Knoten in Chains vergr��ern zwar die Anzahl verf�gbarer Chains, ben�tigen jedoch auch viel Rechenzeit bei der Suche. Au�erdem existieren f�r die meisten der m�glichen zus�tzlichen Chains �quivalente ALS-Techniken (ALS-XZ, ALS-XY oder ALS Chains).

Sonstiges:

ERs mit zwei Kandidaten erlauben: Wenn diese Option nicht gew�hlt ist, werden Empty Rectangles nur gefunden, wenn sie mindestens zwei Kandidaten im Block, der das ER enth�lt, besitzen. ERs mit nur zwei Kandidaten werden als Turbot Fish oder als X-Chain gelistet.
'0' f�r Zwischenablage: Verwendet '0' statt '.' beim Export von Sudokus in die Zwischenablage.
Duals/Siamese erlauben: Erlaubt das Finden von Dual Empty Rectangles, Dual 2-String-Kites und Siamese Fish. Die F�higkeiten des Solvers werden dadurch nicht beeinflusst: Alle Duals/Siamese Fishes werden auch als zwei getrennte L�sungsschritte gefunden.
Fehlende Kandidaten in URs: Wenn gew�hlt, muss das UR nicht komplett sein (es m�ssen nicht in allen UR-Zellen alle UR-Kandidaten vorhanden sein, siehe Unique Rectangles mit fehlenden Kandidaten).

ALS allgemein:

ALS-�berlappungen erlauben: Ab Version 1.2 sind �berlappungen zwischen nicht benachbarten ALS in ALS Chains generell erlaubt. Diese Option erlaubt zus�tzlich �berlappungen zwischen benachbarten ALS (f�hrt zu drastisch erh�hten Rechenzeiten, produziert jedoch auch interessante L�sungsschritt-Varianten).
Nur eine Technik pro Eliminierung: Nimmt f�r jede Kombination von Eliminierungen jeweils nur den einfachsten verf�gbaren ALS-Schritt (genauer: Den Schritt mit den wenigsten ALS-Zellen insgesamt).