Letzter Ausweg

Inhaltsverzeichnis

Templates (Schablonen)

Templates sind eine Einzelziffer-Muster-Strategie. In einem leeren Sudoku-Gitter gibt es genau 46656 verschiedene M�glichkeiten, alle 9 Instanzen einer Ziffer im Gitter zu platzieren. Jedes Mal, wenn eine Instanz dieser Ziffer tats�chlich gesetzt wird, werden alle Schablonen ung�ltig, die diese Ziffer an dieser Stelle nicht enthalten. Jedes Mal, wenn eine andere Ziffer gesetzt wird, werden alle Schablonen ung�ltig, die die Ziffer an dieser Stelle enthalten. Hat man alle m�glichen Templates berechnet, kann die Ziffer aus allen Zellen eliminiert werden, die nicht noch in mindestens einem Template gesetzt sind, und sie kann in allen Zellen gesetzt werden, die in allen verbleibenden Templates gesetzt sind.

Die Beschreibung sollte bereits klar gemacht haben, dass Templates nicht f�r menschliche Spieler gedacht sind. Sie lassen sich jedoch als Indikatoren verwenden: Wenn keine Template-Eliminierungen m�glich sind, k�nnen keine Einzelziffer-Muster Spielz�ge gefunden werden (man kann sich dann z.B. eine Fischsuche komplett sparen). Die andere Richtung ist nicht unbedingt g�ltig.

Forcing Chain (Zwangskette)

Bevor man sich in Forcing Chains/Nets vertieft, sollte man sicher sein, dass man die Einf�hrung zu Chains wirklich gut verstanden hat.

Forcing Chain ist ein generischer Ausdruck f�r alle Chains, die irgendwie zu einem Widerspruch oder zu einer Verity f�hren und damit etwas erzwingen (jede Discontinuous Nice Loop oder AIC ist gem�� dieser Definition auch eine Forcing Chain). Chains, die f�r sich allein noch keinen Widerspruch herbei f�hren k�nnen, k�nnen zu Multiple Forcing Chains kombiniert werden. Alle Chains zusammen beweisen entweder eine Verity oder einen Widerspruch und erzwingen damit einen Zug.

In einer Verity haben mehrere Chains dasselbe Ergebnis. Wenn sichergestellt ist, dass eine der Voraussetzungen einer der Chains wahr sein muss, muss auch das Ergebnis wahr sein. Beispiele f�r Annahmen, die zu einer Verity f�hren k�nnen:

Bei einem Widerspruch starten alle Chains mit derselben Annahme, f�hren aber zu Resultaten, die nicht alle wahr sein k�nnen. Beispiele f�r Widerspr�che:

Die M�glichkeiten von Multiple Forcing Chains sind nahezu unbeschr�nkt.

Wird eine Forcing Chain in HoDoKu angezeigt, kann die Menge an Links das Bild komplett nutzlos machen. Es ist daher n�tig nur eine Chain darstellen zu k�nnen (siehe Hinweis-Bereich verwenden im Benutzerhandbuch).

Sudoku L�sungstechnik: Beispiel f�r Forcing+Chain+Verity+%28all+chains%29 Sudoku L�sungstechnik: Beispiel f�r Forcing+Chain+Verity+%28only+chain+1%29 Sudoku L�sungstechnik: Beispiel f�r Forcing+Chain+Verity+%28only+chain+2%29 Sudoku L�sungstechnik: Beispiel f�r Forcing+Chain+Verity+%28only+chain+3%29

Das Beispiel zeigt eine eher einfache Forcing Chain Verity, die beweist, dass r1c7 4 sein muss (das erste Bild zeigt alle Links auf ein Mal, die anderen drei Bilder zeigen die einzelnen Chains).

Forcing Chain Verity => r1c7=4

Bedeutung: F�r jede m�gliche Platzierung der Ziffer 1 in Zeile 4 kann bewiesen werden, dass r1c7 4 sein muss. r1c7 muss daher wirklich 4 sein.

F�r jede Forcing Chain Verity gibt es eine komplement�re Forcing Chain Contradiction. Die Contradiction f�r das obige Beispiel:

Forcing Chain Contradiction in r4 => r1c7=4

Bedeutung: Wenn r1c7 nicht 4 ist, kann Zeile 4 keine Ziffer 1 enthalten. Da das nicht erlaubt ist, muss die Annahme falsch sein, 4 kann in r1c7 platziert werden.

Forcing Net (Zwangsnetz)

Ein Forcing Net baut auf den gleichen Prinzipien auf wie eine Forcing Chain, nur als Net und nicht als Chain (siehe Chains versus Nets). Forcing Net ist eine Methode, die wirklich nur als letzter Ausweg verwendet werden sollte. Manuell k�nnen Forcing Nets nur von sehr erfahrenen Spielern gefunden werden (die Bilder f�r das Beispiel sprechen eine deutliche Sprache).

Notation: Die Verzweigungen des Netzes werden in Klammern gesetzt. Die Folgerungen werden sp�ter im Netz ben�tigt.

Sudoku L�sungstechnik: Beispiel f�r Forcing+Net+Verity+%28all+chains%29 Sudoku L�sungstechnik: Beispiel f�r Forcing+Net+Verity+%28only+net+1%29 Sudoku L�sungstechnik: Beispiel f�r Forcing+Net+Verity+%28only+net+2%29 Sudoku L�sungstechnik: Beispiel f�r Forcing+Net+Verity+%28only+net+3%29

Das Beispiel ist eine Verity, die beweist, dass r1c2 5 sein muss.

Forcing Net Verity => r1c2=5

Bedeutung: Zelle r7c2 hat nur drei M�glichkeiten �brig: 6, 7 und 9. Unabh�ngig davon, welche dieser Ziffern tats�chlich gesetzt werden wird, muss r1c2 immer 5 sein.

Betrachten wir das letzte (und einfachste) Netz: Wenn wir die Klammern erst einmal ignorieren, k�nnen wir der Chain normal folgen. Wenn r7c2 9 ist, kann r3c2 nicht 9 sein. Hier bleiben wir stecken. Wir k�nnen nicht fortfahren, weil 9 in r3c2 und r1c3 nur durch einen Weak Link verbunden ist. Gl�cklicherweise kann auch r1c2 nicht 9 sein, wenn r7c2 9 ist (der Zweig des Netzes), was den Weak Link in einen Strong Link umwandelt.

Dei Verzweigungen in den anderen Netzen k�nnen nicht so leicht erkl�rt werden. Versuchen Sie es ruhig einmal selbst.

Kraken Fish (Kraken)

Ein Kraken ist eine Kombination eines Fisches mit einer oder mehreren Chains. Er verwendet normalerweise Finned Fish, die keine Eliminierungen bewirken k�nnen, weil keine der m�glichen Eliminierungen alle Fins sehen kann (siehe Fisch Allgemein).

Kraken Fish Type 1

In einem Finned Fish wird eine m�gliche Eliminierung zu einer tats�chlichen, wenn sie alle Fins sehen kann. Leider ist das eher selten der Fall. Oft erh�lt man einen nutzlosen Finned Fish ohne Eliminierungen. Ein Kraken Fish kann auch aus solchen Fischen oft noch eine Eliminierung herausholen, indem er Chains verwendet.

Die Voraussetzung f�r einen Finned Fish war: Wenn alle Fins falsch sind, sind alle m�glichen Eliminierungen g�ltig. Ist aber auch nur eine Fin gesetzt, wird der Fisch ung�ltig und die Platzierung eliminiert den Kandidaten aus allen Zellen, die die Fin sehen k�nnen.

Beim Kraken Fish wird dieses Prinzip einfach erweitert: Wenn wir beweisen k�nnen, dass eine m�gliche Eliminierung f�r alle m�glichen Fins auch falsch sein muss, k�nnen wir sie eliminieren. F�r den Beweis verwenden wir Chains, die mit einem Weak Link in jeder Fin-Zelle beginnen und ebenfalls mit einem Weak Link in der Zelle mit der m�glichen Eliminierung enden.

Sudoku L�sungstechnik: Beispiel f�r Kraken+Fish+Type+1+%28Chain+1%29 Sudoku L�sungstechnik: Beispiel f�r Kraken+Fish+Type+1+%28Chain+2%29

Das Beispiel ist vom selben Sudoku, in dem vorher das Forcing Net n�tig wurde. Die Basis bildet ein Finned Franken X-Wing: 2 r6b2 c57 fr6c2 fr6c9. M�gliche Eliminierungen sind r158c7 (keine der drei sieht alle Fins).

Das linke Bild zeigt die erste Chain, die Fin r6c2 mit Zelle r8c7 verbindet: r6c2 -2- ALS:r4c2,r5c13 -4- r2c1 =4= r2c6 -4- r8c6 =4= r8c7. Das rechte Bild zeigt die zweite Chain f�r die zweite Fin (r6c9): r6c9 -2- ALS:r13479c9 -8- ALS:r8c238 -2- r8c7.

Bedeutung:

Das ist eine typische Verity.

Kraken Fish Type 2

Typ zwei ist ein bisschen komplizierter als Typ 1. Wiederholen wir, wie ein Fisch funktioniert: Ein Fisch garantiert, dass in jedem Cover-Set genau ein Basekandidat gesetzt ist.

Wenn wir Chains finden k�nnen, die jeweils mit einem Weak Link starten und von jedem Basekandidaten in einem der Cover-Sets (plus von jeder Fin, wenn n�tig) alle zum gleichen Ergebnis f�hren, haben wir eine Forcing Chain Verity.

Sudoku L�sungstechnik: Beispiel f�r Kraken+Fish+Type+2+%28Fish+only%29 Sudoku L�sungstechnik: Beispiel f�r Kraken+Fish+Type+2+%28Chain+1%29 Sudoku L�sungstechnik: Beispiel f�r Kraken+Fish+Type+2+%28Chain+2%29 Sudoku L�sungstechnik: Beispiel f�r Kraken+Fish+Type+2+%28Chain+3%29

Das Beispiel zeigt einen Kraken Fish, der auf einem Sashimi X-Wing beruht: 4 r15 c12 fr1c7 fr1c9. Was gut f�r uns ist, ist dass Cover-Set Spalte 2 nur einen Basekandidaten hat (r5c2). Die andere 4 in dieser Spalte (r3c2) ist ein Coverkandidat und interessiert uns hier nicht weiter. Wir k�nnen folgende Chains finden:

Gemeinsam beweisen sie, dass r5c9 nicht 7 sein kann.

Brute Force (Rohe Gewalt)

Brute Force ist nicht wirklich eine Strategie: Wir platzieren eine Ziffer in einer Zelle und schauen, ob wir eine L�sung erhalten oder nicht. Wenn diese Methode aktiviert ist, kann jedes Sudoku gel�st werden.

Copyright © 2008-12 by Bernhard Hobiger
Alles Material auf dieser Site unterliegt der GNU FDLv1.3.