WaBis

walter.bislins.ch

Sudoku: Hidden Subsets

In einem Hidden Subset (Versteckte Untermenge) kommen N bestimmte Kandidaten versteckt unter anderen Kandidaten in genau N Zellen des selben Hauses vor. Diese N Kandidaten bezeichnet man als Subset der Grösse N. Weil die N Kandidaten des Subsets in genau N Zellen vorkommen, teilen sie die N Zellen unter sich auf. Alle Kandidaten in diesen N Zellen, die nicht zum Subset gehören, können daher gelöscht werden.

Zu beachten ist, dass nicht in jeder der N Zellen alle Kandidaten des N-Subsets enthalten sein müssen (Ausnahme Hidden Pair).

Hidden Subsets gibt es in Set-Grössen von 2 bis 7. Weil Hidden Subsets mit grossem N komplementär zu Naked Subsets mit kleinem N sind und weil letztere oft einfacher zu finden sind, beschränkt sich die Suche in der Praxis auf Hidden Pairs (N = 2) und Hidden Triples (N = 3).

Weil die Methoden Naked Subsets und Hidden Subsets zueinander komplementär sind, verwendet die Sudoku-App denselben Algorithmus für beide Methoden. Lediglich die Markierung der Kandidaten unterscheidet sich bei den beiden Methoden.

 Hidden Subsets sind zu Naked Subsets komplementär

Beispiel Hidden Pair in Box

Ein Hidden Pair (Verstecktes Paar) ist ein Hidden Subset mit 2 Kandidaten. Wenn in einem Haus 2 bestimmte Kandidaten versteckt unter anderen Kandidaten in genau 2 Zellen vorkommen, bilden sie ein Hidden Pair. Da diese beiden Kandidaten in keiner anderen Zelle des Hauses vorkommen, teilen sie diese beiden Zellen unter sich auf. Alle übrigen Kandidaten, die nicht zum 2-er Subset gehören, können aus diesen beiden Zellen gelöscht werden.

Kandidaten-Gitter
Hidden Pair Kandidaten-Gitter

Kandidaten-Gitter
Hidden Pair Kandidaten-Gitter mit Scan-Lines

Code: 000060000 000042736 006730040 094000068 000096407 607050923 100000085 060080271 005010094 [1]

In diesem Beispiel kommen die 2 grün markierten Kandidaten 4 und 7 der orangen Box nur in 2 Zellen vor. Da die beiden Kandidaten in keiner anderen Zelle der Box vorkommen, teilen sie die beiden Zellen unter sich auf. Alle rot markierten Kandidaten können gelöscht werden.

Hidden Pairs finden

Wie die zweite Abbildung oben zeigt können Hidden Pairs ähnlich wie Hidden Singles durch Scannen gefunden werden. In den beiden blauen Zeilen sowie in der grünen Spalte kommen jeweils die beiden Zahlen 4 und 7 vor. Sie sperren nach den Sudoku-Regeln die meisten Zellen von Box 1 für diese beiden Zahlen. Für die 4 und 7 bleiben nur noch die beiden weissen Zellen von Box 1 übrig. Das heisst, dass in diesen beiden Zellen keine anderen Lösungs-Zahlen stehen kann. Somit können alle Kandidaten aus diesen beiden Zellen gelöscht werden, mit Ausnahme der 4 und 7.

Beispiel Hidden Pair in Spalte

Kandidaten-Gitter
Hidden Pair Kandidaten-Gitter

Kandidaten-Gitter
Hidden Pair Kandidaten-Gitter mit Markierungen

Code: 049132000 081479000 327685914 096051800 075028000 038046005 853267000 712894563 964513000 [2]

Bei diesem Beispiel gibt es ein grün markiertes Hidden Pair 19 in der orangen Spalte. Hier ist das Paar nicht vollständig versteckt und daher kaum als solches erkennbar.

Finden kann man auch dieses Paar mit der Scan-Methode: In den Zeilen 1, 2, 4 und 9 kommen die beiden Zahlen 1 und 9 jeweils in den grünen Zellen vor. Nach den Sudoku-Regeln können diese Zahlen in den violetten Zellen der letzten Spalte nicht mehr vorkommen. In der letzten Spalte bleiben für die 1 und 9 nur noch die beiden hellblauen Felder übrig. In diesen beiden Feldern muss sich das Hidden Pair 19 verstecken.

Beispiel Hidden Triple in Box

Ein Hidden Triple (Versteckte Dreiergruppe) ist ein Hidden Subset mit 3 Kandidaten. Wenn in einem Haus 3 bestimmte Kandidaten versteckt unter anderen Kandidaten in 3 Zellen vorkommen, bilden sie ein Hidden Triple. Da diese 3 Kandidaten in keiner anderen Zelle des Hauses vorkommen, teilen sie diese 3 Zellen unter sich auf. Alle übrigen Kandidaten, die nicht zum 3-er Subset gehören, können aus diesen drei Zellen gelöscht werden.

Kandidaten-Gitter
Hidden Triple Kandidaten-Gitter

Kandidaten-Gitter
Hidden Triple Kandidaten-Gitter mit Markierungen

Code: 280000473 534827196 071034080 300500040 000340060 460790310 090203654 003009821 000080937 [3]

In diesem Beispiel kommen die 3 grün markierten Kandidaten 245 der orangen Box nur in 3 Zellen vor. Da diese 3 Kandidaten in keiner anderen Zelle der Box vorkommen, teilen sie die 3 Zellen unter sich auf. Alle rot markierten Kandidaten können gelöscht werden.

Finden kann man diese Dreiergruppe mit der Scan-Methode: In der Zeile 7 und der Spalte 1 kommen die drei Zahlen 2, 4 und 5 jeweils in den grünen Zellen vor. Nach den Sudoku-Regeln können diese drei Zahlen in den violetten Zellen von Box 7 nicht mehr vorkommen. Diese drei Zahlen müssen sich somit irgendwie auf die drei übrig gebliebenen hellblauen Zellen der Box verteilen. Alle nicht zum 3-er Subset 245 gehörenden Kandidaten können aus den hellblauen Zellen gelöscht werden.

Beispiel Hidden Triple in Spalte

Kandidaten-Gitter
Hidden Triple Kandidaten-Gitter

Kandidaten-Gitter
Hidden Triple Kandidaten-Gitter mit Markierungen

Code: 500620037 004890000 000050000 930000000 020000605 700000003 000009000 000000700 680570002 [4]

In diesem Beispiel kommen die 3 grün markierten Kandidaten 256 in der orangen Spalte nur in 3 Zellen vor. Da diese 3 Kandidaten in keiner anderen Zelle der orangen Spalte vorkommen, teilen sie die 3 Zellen unter sich auf. Alle rot markierten Kandidaten können gelöscht werden.

Finden kann man diese Dreiergruppe ebenfalls mit der Scan-Methode: In der Box 2 und den Zeilen 5 und 9 kommen die drei Zahlen 2, 5 und 6 jeweils in den grünen Zellen vor. Nach den Sudoku-Regeln können diese drei Zahlen in den violetten Zellen von Spalte 6 nicht mehr vorkommen. Diese drei Zahlen müssen sich somit irgendwie auf die drei übrig gebliebenen hellblauen Zellen der Spalte verteilen. Alle nicht zum 3-er Subset 256 gehörenden Kandidaten können aus den hellblauen Zellen gelöscht werden.

Hidden Subsets sind zu Naked Subsets komplementär

Zu allen Naked Subsets gibt es komplementäre Hidden Subsets und umgekehrt. In beiden Varianten können exakt dieselben Kandidaten gelöscht werden. Die komplementären Subsets sind nur verschiedene Betrachtungsweisen derselben Konstellation.

Die Kandidaten des Hidden Subsets zusammen mit den Kandidaten des komplementären Naked Subsets ergeben alle im betrachteten Haus noch möglichen Kandidaten:

Kandidaten-Gitter mit Hidden Triple
Hidden Triple Kandidaten-Gitter

Kandidaten-Gitter mit Naked 5-Tuple
Naked 5-Tuple Kandidaten-Gitter

In obigem Beispiel steht in der orangen Spalte die Lösungs-Zahl 9. Es bleiben die Kandidaten 1-8 für diese Spalte übrig. Das erste Bild zeigt, dass es in dieser Spalte ein Hidden Triple aus den grün markierten Kandidaten 256 gibt. Das zweite Bild zeigt das komplementäre Naked 5-Tuple aus den noch verbleibenden grün markierten 5 Kandidaten 13478.

Mit beiden Methoden können dieselben rot markierten Kandidaten gelöscht werden. Welche Methode einfacher zu finden ist, hängt von den jeweiligen Subset-Grössen ab und wie die Subset-Kandidaten auf die Zellen verteilt sind.

Es gilt folgende Gesetzmässigkeit für die komplementären Subsets:

Grösse des Hidden Subset = 9 - Anzahl Lösungszahlen - Grösse des Naked Subsets

Im Beispiel gibt es eine Lösungszahl und das Naked Subset hat die Grösse 5. Daraus ergibt sich eine Subset-Grösse von 9 - 1 - 5 = 3 für das komplementäre Hidden Subset.

Die Sudoku-App verwendet intern für Naked Subsets und Hidden Subsets denselben Algorithmus, der nur nach Naked Subsets sucht. Soll ein Hidden Subset der Grösse N in einem bestimmten Haus gesucht werden, so wird berechnet, wie gross das komplementäre Naked Subset ist und es wird nach einem Naked Subset dieser Grösse gesucht. Der Algorithmus markiert aber je nachdem die Kandidaten des einen oder anderen Subsets grün. Weil derselbe Algorithmus für Naked und Hidden Subsets verwendet wird, haben komplementäre Subsets denselben Level.

Wenn die Option Alle Methoden berechnen aktiviert ist, berechnet die Sudoku-App alle komplementären Subsets. Ansonsten wird nur die Methode mit dem kleineren Subset in die Liste der gefundenen Methoden aufgenommen. Zu jeder Konstellation gibt es meist mehrere anwendbare Methoden um einen Schritt weiter zu kommen. Mit den Selektions-Buttons kann eine dieser Methode ausgewählt werden.

Folgendes Sudoku zeigt sehr schön die verschiedenen komplementären Konstellationen:

Code: 1(239)(23579)(23579)(235)648(35) (2789)64(235789)(2358)(23579)(29)(135)(135) (289)(2389)(23589)(123589)4(12359)(29)67 (28)(12348)(1238)(12358)9(1235)67(2348) (2689)7(123689)4(12368)(123)5(39)(2389) 5(23489)(23689)(2368)7(23)1(349)(23489) (6789)5(16789)(19)(16)432(169) 3(129)(1269)(12569)(1256)87(1459)(14569) 4(129)(1269)(1235679)(12356)(123579)8(159)(1569)

Klicke auf obigen Link, aktiviere die Option Alle Methoden berechnen und vergleiche die 4 gefundenen Methoden miteinander durch Verwenden der Selektions-Buttons.

Weitere Beispiele mit Hidden Subsets

Quellen

hodoku.sourceforge.net
http://hodoku.sourceforge.net/de/show_example.php?file=h202&tech=Hidden+Pair
hodoku.sourceforge.net
http://hodoku.sourceforge.net/de/show_example.php?file=h201&tech=Hidden+Pair
hodoku.sourceforge.net
http://hodoku.sourceforge.net/de/show_example.php?file=h301&tech=Hidden+Triple
hodoku.sourceforge.net
http://hodoku.sourceforge.net/de/show_example.php?file=h302&tech=Hidden+Triple
Weitere Infos zur Seite
Erzeugt Sonntag, 17. Februar 2013
von wabis
Zum Seitenanfang
Geändert Sonntag, 6. Dezember 2015
von wabis