Uniqueness (Eindeutigkeit)
Inhaltsverzeichnis
- Einf�hrung
- Unique Rectangle Type 1 (Ausschlussrechteck Typ 1)
- Unique Rectangle Type 2 (Ausschlussrechteck Typ 2)
- Unique Rectangle Type 3 (Ausschlussrechteck Typ 3)
- Unique Rectangle Type 4 (Ausschlussrechteck Typ 4)
- Unique Rectangle Type 5 (Ausschlussrechteck Typ 5)
- Unique Rectangle Type 6 (Ausschlussrechteck Typ 6)
- Hidden Rectangle (Verstecktes Rechteck)
- Avoidable Rectangle (Vermeidbares Rechteck)
- BUG+1 - Binary Universal Grave + 1 (Zweiwertiges Zifferngrab + 1)
- Unique Rectangles mit fehlenden Kandidaten
Einf�hrung
Eindeutigkeit in Sudoku
Uniqueness Techniques (Eindeutigkeits-Strategien) basieren auf der Tatsache, dass praktisch jedes jemals publizierte Sudoku lediglich eine einzige g�ltige L�sung besitzt. Mehr noch: Die meisten Sudoku-Spieler sind der Meinung, dass Sudokus mit mehr als einer L�sung ung�ltig sind. Das bedeutet aber, dass jede Konstellation, die zu zwei oder mehr L�sungen f�hren k�nnte, die alle die Sudoku-Regel nicht verletzen, vermieden werden muss. Das Problem dabei ist, dass Eindeutigkeit von Sudokus nicht Teil der Sudoku-Regel ist ("jede Zeile, jede Spalte und jeder Block muss die Ziffern 1 bis 9 enthalten"). Das hat zu einer sehr hitzigen Diskussion dar�ber gef�hrt, ob Uniqueness Strategien erlaubt sind oder nicht (siehe Uniqueness Controversy auf Sudopedia).
Ob man nun Uniqueness Strategien einsetzt oder nicht, ist zur G�nze eine Frage des pers�nlichen Geschmacks. Wenn man Sudokus l�st, die in B�chern oder Zeitungen ver�ffentlicht wurden, kann man hinreichend sicher sein, dass sie nur eine eindeutige L�sung besitzen (f�r einige Ausnahmen siehe Hall of Shame). Wenn man ein Computerprogramm wie HoDoKu verwendet, wird die Anzahl der L�sungen bei der Eingabe automatisch gepr�ft, und das Programm gibt eine Warnung aus, wenn man versucht ein ung�ltiges Sudoku zu l�sen (siehe auch das Benutzerhandbuch).
Uniqueness Strategien sind einfach zu finden, vielseitig und k�nnen oft Sudokus l�sen, die sonst sehr komplizierte Strategien ben�tigen w�rden. HoDoKu hat daher Unterst�tzung f�r eine Vielzahl an Strategien eingebaut. Will man sie nicht verwenden (trotz ihrer offensichtlichen Vorteile), kann man alle Uniqueness Strategien mit einem einzigen Mausklick ausschalten ("Bearbeiten|Einstellungen", auf die Baumansicht umschalten).
Unique Rectangle (Ausschlussrechteck)
Ein Unique Rectangle (UR) besteht aus vier Zellen, die genau zwei Zeilen, zwei Spalten und zwei Bl�cke belegen. Alle vier Zellen haben dieselben zwei Kandidaten �brig.
Das linke Beispiel ist dem Artikel Unique Rectangle der Sudopedia entnommen. Die Zellen r2c13 und r4c13 erf�llen alle n�tigen Anforderungen. Zwei Zeilen (Zeilen 2 und 4), zwei Spalten (Spalten 1 und 3), zwei Bl�cke (Bl�cke 1 und 4) und zwei Kandidaten (Kandidaten 6 und 8).
Eine Situation wie oben beschrieben ist ung�ltig, weil die Kandidaten in den Zellen vertauscht werden k�nnen und so zwei verschiedene L�sungen erzeugen, die beide die Sudoku-Regel nicht verletzen (siehe unten). Wenn das Sudoku nur eine L�sung hat, muss jede Situation, die zu einem Unique Rectangle f�hren k�nnte, vermieden werden.
Die zwei (g�ltigen) L�sungen f�r das obige UR:
Ein beliebter Fehler beim Suchen von URs besteht darin, die "zwei Bl�cke"-Regel zu verletzen (siehe Sudopedia Artikel f�r ein Beispiel).
Binary Universal Grave (BUG) (Zweiwertiges Zifferngrab)
Ein Binary Universal Grave (BUG) ist eine Verallgemeinerung eines UR: Ein BUG existiert, wenn alle noch ungel�sten Zellen genau zwei Kandidaten haben und wenn jeder Kandidat in jeder Zeile, jeder Spalte und jedem Block genau zwei Mal vorkommt. Auch ein solches Sudoku hat zwei g�ltige L�sungen.
Unique Rectangle Type 1 (Ausschlussrechteck Typ 1)
Ein UR Typ 1 existiert, wenn genau eine Zelle eines m�glichen URs zus�tzliche Kandidaten hat. W�rden diese Kandidaten gel�scht, w�rde das UR existieren und zwei L�sungen bewirken. Es ist daher absolut notwendig einen der zus�tzlichen Kandidaten zu setzen. Das bedeutet, dass die UR-Kandidaten aus dieser Zelle gel�scht werden k�nnen. Wenn es nur einen zus�tzlichen Kandidaten gibt, kann er sofort in der Zelle platziert werden.
Im linken Beispiel bilden die Kandidaten 8 und 9 beinahe ein UR in r2c23 und r6c23. Das UR wird nur durch den zus�tzlichen Kandidaten 3 in r2c2 verhindert. 8 und 9 k�nnen aus r2c2 eliminiert werden (oder 3 kann in r2c2 platziert werden).
Rechtes Beispiel: 2/3 in r2c46,r9c46 => r9c6<>23 (oder r9c6=1).
Unique Rectangle Type 2 (Ausschlussrechteck Typ 2)
Wenn in einem m�glichen UR zwei nicht diagonale Zellen genau den gleichen zus�tzlichen Kandidaten haben, k�nnen alle Kandidaten, die beide Extra-Kandidaten sehen, eliminiert werden.
Die Logik ist einfach: Um das UR zu vermeiden muss einer der beiden zus�tzlichen Kandidaten gesetzt werden, daher kann der Kandidat in keiner Zelle gesetzt sein, die beide diese Zellen sieht.
Linkes Beispiel: Wir haben ein m�gliches UR f�r 3 und 7 in r7c29 und r8c29. Die beiden nicht diagonalen Zellen r78c9 haben einen Zusatzkandidaten 8. Eine dieser beiden Zellen muss 8 sein, sonst h�tte das Sudoku zwei L�sungen. 8 kann daher auf keinen Fall in r9c9 gesetzt werden.
Ein UR Type 2 kann Kandidaten in mehr als einem Haus eliminieren, wie das rechte Beispiel zeigt: Die zus�tzlichen 7er in r8c56 eliminieren alle anderen 7er sowohl in Zeile 8 als auch in Block 8.
Unique Rectangle Type 3 (Ausschlussrechteck Typ 3)
Diese Strategie kombiniert ein UR mit einem Naked/Locked Subset. Man sucht zwei nicht diagonale Zellen mit Zusatzkandidaten in einem m�glichen UR. Da einer dieser Kandidaten gesetzt sein muss um das UR zu vermeiden, k�nnen beide Zellen als eine virtuelle Zelle aufgefasst werden, die nur die Zusatzkandidaten enth�lt. Mit dieser virtuellen Zelle kann man jetzt versuchen, ein Naked Subset zu bilden (alle zus�tzlichen Zellen m�ssen nat�rlich beide UR-Zellen sehen k�nnen). Wenn so eine UR/Naked Subset-Kombination gefunden werden kann, k�nnen alle Subset-Kandidaten in allen Zellen au�erhalb des Subsets (aber nat�rlich im selben Haus) eliminiert werden.
Linkes Beispiel: M�gliches UR f�r 1/5 in r4c28 und r6c28. Zelle r6c8 hat zwei zus�tzliche Kandidaten 6 und 9 und Zelle r4c8 hat zwei zus�tzliche Kandidaten 4 und 6. Wenn wir Zellen r46c8 als eine Zelle auffassen, die nur die Kandidaten 4, 6 und 9 enth�lt, k�nnen wir ein Naked Triple f�r diese drei Kandidaten in den Zellen r1c8, r2c8 und r46c8 bilden. Da die drei Kandidaten auf diese vier Zellen beschr�nkt sind, k�nnen sie weder in r8c8 noch in r9c8 gesetzt werden.
Das rechte Beispiel zeigt ein UR Type 3 mit einem Locked Pair: Die zus�tzlichen Kandidaten 1 und 3 in r6c23 bilden das Locked Pair mit r6c1 (eingeschlossen in Zeile 6 und Block 4).
Unique Rectangle Type 4 (Ausschlussrechteck Typ 4)
Man sucht wieder nach Zusatzkandidaten in zwei nicht diagonalen Zellen, aber dieses Mal werden die Zusatzkandidaten ignoriert, man konzentriert sich auf die UR-Kandidaten: Wenn einer der UR-Kandidaten in dem Haus, das die beiden Extra-Zellen enth�lt, nirgendwo sonst mehr vorkommen kann, kann der andere UR-Kandidat aus diesen Zellen eliminiert werden.
Um zu sehen, wie das funktioniert, betrachten wir das linke Beispiel: M�gliches UR f�r 6/7 in r3c79 und r6c79. r3c7 und r3c9 haben Zusatzkandidaten (das hei�t: das sind die einzigen Zellen des URs, die �berhaupt weder 6 noch 7 sein k�nnen). Es gibt zwei H�user, die sowohl die Zelle r3c7 als auch die Zelle r3c9 sehen k�nnen; Zeile 3 und Block 3. Zeile 3 hat den Kandidaten 6 nur in den UR-Zellen (das gilt auch f�r Block 3, aber das ist nicht n�tig - ein Haus reicht v�llig), also muss 6 entweder in r3c7 oder in r3c9 gesetzt werden. Das aber hei�t, dass 7 weder in r3c7 noch in r3c9 gesetzt sein darf, sonst h�tten wir ja ein UR. Wir k�nnen also 7 aus r3c79 eliminieren.
Die gleiche Logik gilt f�r das rechte Beispiel: UR-Kandidat 8 ist nirgendwo sonst in Spalte 8 (oder Block 9) m�glich, also kann 2 eliminiert werden. Man sollte beachten, dass zus�tzliche Kandidaten 8 in einem der beiden H�user (Spalte 8 oder Block 8) vorhanden sein d�rften, allerdings nicht in beiden. So eine Situation ist aber nicht sehr wahrscheinlich, weil die zus�tzlichen 8er normalerweise vorher mit einem Locked Candidates-Zug eliminiert worden w�ren.
Unique Rectangle Type 5 (Ausschlussrechteck Typ 5)
UR Typ 5 ist eine Variante von UR Typ 2, hier kann der Zusatzkandidat allerdings auch in diagonalen Zellen sein. Nehmen wir an, wir h�tten ein m�gliches UR mit einem Zusatzkandidaten in entweder zwei diagonalen oder aber in drei Zellen des URs. Der Zusatzkandidat kann aus allen Zellen gel�scht werden, die alle UR-Zellen mit diesem Kandidaten sehen k�nnen. Die Logik hinter dieser Strategie ist ganz gleich wie beim UR Type 2.
Das linke Beispiel ist das einzige derzeit ver�ffentlichte Beispiel f�r ein UR Typ 5 mit nur zwei Zusatzkandidaten: 1 muss entweder in r7c8 oder in r8c5 gesetzt sein um das UR zu vermeiden. Zelle r7c4 sieht diese beiden UR-Zellen und kann daher selber nicht 1 sein.
Das UR Type 5 im rechten Beispiel hat drei Zusatzkandidaten: 6 muss in r8c6, r8c9 oder r9c9 sein. Es kann aus r8c7 gel�scht werden.
Unique Rectangle Type 6 (Ausschlussrechteck Typ 6)
UR Typ 6 ist eine Variante von UR Typ 4. Es ist nicht sehr h�ufig, aber sehr effektiv, weil es immer zu zwei Platzierungen f�hrt: Angenommen es existiert ein m�gliches UR mit zwei diagonalen Zellen mit Zusatzkandidaten. Wenn einer der UR-Kandidaten in den beiden Zeilen und Spalten, die das UR bilden, nirgendwo au�erhalb des URs vorkommen kann, kann er aus den Zellen mit den Zusatzkandidaten gel�scht werden.
Linkes Beispiel: In Zeilen 4 und 5 und Spalten 3 und 4 existiert Kandidat 5 nur mehr im UR: Er bildet einen X-Wing. W�rde 5 in einer der Zellen r4c3/r5c4, die die Zusatzkandidaten enthalten, gesetzt, m�sste 5 in der anderen Zelle ebenfalls gesetzt werden, was ein UR und damit zwei L�sungen erzwingen w�rde. Man kann daher sicher sein, dass 5 in keiner dieser Zellen vorkommen kann.
Das rechte Beispiel zeigt ein UR Typ 6 f�r Kandidat 7. �brigens existiert f�r jedes UR Typ 6 ein Paar von Hidden Rectangles, die beide zu den gleichen Platzierungen f�hren.
Hidden Rectangle (Verstecktes Rechteck)
Hidden Rectangles sind sehr vielseitig, weil sie in m�glichen URs eingesetzt werden k�nnen, die bis zu drei Zellen mit beliebigen Zusatzkandidaten enthalten (das UR ist unter einem Haufen von Zusatzkandidaten versteckt - nicht zu verwechseln mit einem Almost Unique Rectangle).
Man ben�tigt ein m�gliches UR mit zwei oder drei Zellen mit Zusatzkandidaten (gibt es nur eine solche Zelle, sollte das UR Typ 1 verwendet werden). Nun nimmt man eine UR-Zelle ohne Zusatzkandidat als Ausgangspunkt und pr�ft die Zeile und die Spalte, die die schr�g gegen�berliegende Ecke des URs enthalten. Darf einer der UR-Kandidaten in diesen beiden H�usern nirgendwo au�erhalb des URs vorkommen, kann der andere UR-Kandidat aus der gegen�berliegenden Ecke gel�scht werden.
Um zu sehen, warum das funktioniert, betrachten wir das linke Beispiel: Es gibt nur eine Zelle ohne Zusatzkandidaten: r7c7. Diese Zelle wird unser Ausgangspunkt. Die schr�g gegen�berliegende Ecke ist Zelle r9c5, die in Zeile 9 und Spalte 5 enthalten ist. Kandidat 5 kommt au�erhalb des URs in diesen beiden H�usern nicht mehr vor, also kann 9 aus r9c5 gel�scht werden. Warum? Wenn wir Spalte 5 betrachten, sehen wir, dass Kandidat 5 entweder in r7c5 oder in r9c5 gesetzt werden muss. Wenn 5 in r9c5 gesetzt wird, kann diese Zelle nat�rlich nicht 9 sein. Wird 5 in r7c5 gesetzt, kann 5 nicht in r9c5 sein, 5 muss also in r9c7 gesetzt werden. Das zwingt r7c7 auf 9 und das wiederum bedeutet, dass r9c5 nicht auch 9 sein kann, sonst h�tten wir wieder zwei L�sungen. Da beide m�glichen Platzierungen des Kandidaten 5 in Spalte 5 zu r9c7<>9 f�hren, kann 9 aus dieser Zelle gel�scht werden.
Das rechte Beispiel hat nur zwei Zellen mit zus�tzlichen Kandidaten, was bedeutet, dass zwei m�gliche Ausgangspunkte gepr�ft werden m�ssen: r2c9 und r3c2. Versuchen wir zuerst r2c9: Die gegen�berliegende Ecke ist in Zeile 3 und Spalte 2. Wir sehen nun, dass Zeile 3 eine 4 und eine 5 au�erhalb des URs hat, es ist also kein Hidden Rectangle m�glich.
Jetzt r3c2: Die H�user, die gepr�ft werden m�ssen, sind Zeile 2 und Spalte 9. Kandidat 4 gibt es nirgendwo mehr in diesen H�usern (au�er im UR nat�rlich), also kann 5 aus r2c9 gel�scht werden.
Avoidable Rectangle (Vermeidbares Rechteck)
Ein Avoidable Rectangle unterscheidet sich von einem Unique Rectangle dadurch, dass einige Zellen des UR bereits gesetzt worden sind. Wenn das Setzen der restlichen Zellen ein UR bewirkt, dann h�tte der Erzeuger des Sudokus eine der vier Zellen als Angabe setzen m�ssen um eine m�gliche zweite L�sung zu vermeiden (daher der Name). Wenn also keine der bereits gesetzten Zellen Teil der Angabe ist, k�nnen alle UR Type x-Regeln ohne �nderungen angewendet werden.
Einen wichtigen Unterschied gibt es allerdings: Durch die bereits erfolgten Platzierungen kann es vorkommen, dass nur mehr einer der UR-Kandidaten in der Zielzelle �brig ist. Das kann zwar verwirrend sein, aber die Logik der Strategien wird davon nicht beeinflusst.
HoDoKu unterst�tzt derzeit nur Avoidable Rectangles Type 1 und 2.
Avoidable Rectangle Type 1 (Vermeidbares Rechteck Typ 1)
Analog zu Unique Rectangle Type 1.
Linkes Beispiel: Das m�gliche UR ist f�r Kandidaten 7 und 9 in Zellen r12c19. Die einzige noch nicht gesetzte Zelle ist r2c9, alle anderen Zellen geh�ren nicht zur Angabe. Wenn 9 in r2c9 gesetzt w�rde, k�nnten die Ziffern 7 und 9 in den vier UR-Zellen ausgetauscht werden, was zwei L�sungen bewirken w�rde. Da das nicht m�glich ist, kann r2c9 nicht 9 sein.
Wichtig ist, dass die Logik nur angewendet werden kann, wenn keine der Zellen zur Angabe geh�rt. Ist auch nur eine der Zellen in der Angabe enthalten, k�nnen die Ziffern nicht mehr vertauscht werden und es gibt immer noch nur eine L�sung f�r das Sudoku.
Rechtes Beispiel: Avoidable Rectangle Type 1: 6/3 in r57c78 => r5c7<>3
Avoidable Rectangle Type 2 (Vermeidbares Rechteck Typ 2)
Analog zu Unique Rectangle Type 2. Type 2 l��t sich leichter erkennen, weil beide UR-Kandidaten noch als Kandidaten sichtbar sind.
Linkes Beispiel: UR f�r Kandidaten 3 und 7 in r78c37, weder r7c7 noch r8c7 geh�ren zur Angabe. Zus�tzlicher Kandidat 9 in r78c3, 9 kann von allen Zellen gel�scht werden, die diese beiden Zellen sehen.
Rechtes Beispiel: Avoidable Rectangle Type 2: 2/8 in r45c37 => r18c7,r456c9,r56c8<>9
BUG+1 - Binary Universal Grave + 1 (Zweiwertiges Zifferngrab + 1)
Ein BUG+1 ist ein m�glicher BUG, bei dem genau eine Zelle genau einen zus�tzlichen Kandidaten hat. Dieser Kandidat muss platziert werden um den BUG zu vermeiden.
Linkes Beispiel: Der Zusatzkandidat ist Kandidat 6 in r1c8 (kommt �fter als zwei Mal in mindestens einem Haus vor). Er kann gesetzt werden (oder 3 und 5 k�nnen gel�scht werden).
Rechtes Beispiel: Dies ist kein BUG+1! Wir haben zwar nur Zellen mit zwei Kandidaten �brig (Ausnahme: r7c6), aber die Bedingung f�r einen BUG ist nicht erf�llt: In Zeile 7 kommt Kandidat 9 drei mal vor (r7c147). Das Gleiche gilt f�r Spalte 6.
Unique Rectangles mit fehlenden Kandidaten
Damit ein Unique Rectangle funktionieren kann, m�ssen nicht unbedingt alle UR-Kandidaten in allen UR-Zellen vorhanden sein. Die einzige wirklich notwendige Bedingung ist, dass jede UR-Zelle alle UR-Kandidaten enthalten h�tte k�nnen (das bedeutet: kein UR-Kandidat darf in einer UR-Zelle durch eine Zahl der Angabe blockiert sein). Das kann wichtig werden, wenn UR-Kandidaten bereits durch einen fr�heren L�sungsschritt eliminiert worden sind, was nat�rlich das UR ung�ltig machen w�rde, g�lte oben Gesagtes nicht.
HoDoKu erlaubt fehlende Kandidaten in URs, wenn die Option "Fehlende Kandidaten in URs" in "Einstellungen|L�sungsschritte" gesetzt ist (siehe Optionen f�r L�sungstechniken im Benutzerhandbuch).
Einige Beispiele:
Linke Seite: UR Typ 1; r3c4 enth�lt den UR-Kandidaten 2 nicht mehr, aber 2 ist auch nicht durch die Angabe blockiert, daher ist das UR Typ 1 trotzdem g�ltig. Rechte Seite: UR Typ 2; UR-Kandidat 5 fehlt von r3c8.
Linke Seite: UR Typ 6, UR-Kandidat 8 fehlt in r3c9 und r6c7; die Eliminierungen sind trotzdem g�ltig. Rechte Seite: Hidden Rectangle, Kandidat 3 fehlt in r2c9 und r3c6.
Copyright © 2008-12 by Bernhard Hobiger
Alles Material auf dieser Site unterliegt der GNU FDLv1.3.