WaBis

walter.bislins.ch

Sudoku: Naked Subsets

In einem Naked Subset (Nakte Untermenge) kommen N verschiedene Kandidaten in genau N Zellen des selben Hauses exklusiv vor. Diese N Kandidaten bezeichnet man als Subset der Grösse N. In keiner dieser N Zellen kommt ein Kandidat vor, der nicht zu diesem Subset der Grösse N gehört. Die Kandidaten des N-Subsets besetzen also auf noch nicht bekannte Art genau diese N Zellen. Damit alle N Zellen einen der N Kandidaten abbekommen, darf keiner der N Kandidaten in einer andere Zelle des selben Hauses vorkommen. Entsprechende Kandidaten in anderen Zellen des selben Hauses können also gelöscht werden.

Naked Subsets findet man nur, wenn man das Kandidaten-Gitter zuhilfe nimmt. Naked Subsets gibt es in Set-Grössen von 2 bis 7:

Zu beachten ist, dass in den N Zellen jeweils nicht immer alle Kandidaten des N-Subsets enthalten sein müssen (Ausnahme Naked Pair).

Naked Subsets und Hidden Subsets sind zu einander komplementär. Für jedes Naked Subset gibt es ein passendes Hidden Subset. In der Regel ist es so, dass einem Naked Subset mit grossem N ein Hidden Subset mit einem kleinen N entspricht und umgekehrt. Es ist oft leichter, ein Hidden Pair oder ein Hidden Triple zu finden, als ein grosses Naked N-Tuple. Andereseits ist es viel leichter, ein Naked Pair oder ein Naked Triple zu finden, als ein grösseres Hidden Subset.

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 Naked Pair in Zeile

Ein Naked Pair (Naktes Paar) ist ein Naked Subset mit zwei Kandidaten. Wenn man zwei Zellen im selben Haus finden kann, die beide nur noch dieselben zwei Kandidaten enthalten, kann man diese Kandidaten aus allen anderen Zellen des Hauses löschen.

Zahlen-Gitter
Naked Pair

Kandidaten-Gitter
Naked Pair Kandidaten-Gitter

Code: 000000200 058706390 600300085 813475629 006000537 527639148 760008953 005907810 089003000

In diesem Beispiel betrachten wir die orange Zeile. In ihr gibt es zwei Zellen, welche exklusiv das grün markierte Kandidaten-Paar 14 enthalten. In einer dieser Zellen muss also eine 1 in der anderen eine 4 stehen, andere Kandidaten gibt es für diese zwei Zellen nicht. Welche Zahl in welcher dieser beiden Zellen zu stehen kommt, wissen wir noch nicht. Wir können aber ausschliessen, dass die Zahlen 1 und 4 in einer anderen Zelle der orangen Zeile stehen können. Deshalb können wir die rot markierten Kandidaten 1 und 4 aus allen anderen Zellen dieser Zeile streichen.

Durch das Löschen der rot markierten Kandidaten bleibt in der gelben Zelle nur noch der Kandidat 6 übrig. Wir können also im nächsten Schritt die Zahl 6 in die gelbe Zelle setzen.

Beispiel Naked Pair in Box

Zahlen-Gitter
Naked Pair in Box

Kandidaten-Gitter
Naked Pair in Box Kandidaten-Gitter

Code: 793608041 258741963 461039870 320190680 589463010 610080009 146900008 935806020 872304096

In diesem Beispiel gibt es ein Naked Pair mit den grün markierten Kandidaten 27 in der orangen Box. Diese Kandidaten können in allen anderen Zellen der orangen Box gestrichen werden (rot markiert).

Die so übrig gebliebenen Kandidaten 345 in den 3 anderen nicht besetzen Zellen bilden übrigens dann ein Naked Triple. Vor dem Löschen der rot markierten Kandidaten bilden die Kandidaten 345 in diesen 3 Zellen ein Hidden Triple. Wie man sieht sind also Naked und Hidden Subsets komplementäre Methoden.

Beispiel Naked Triple in Box

Ein Naked Triple (Nakte Dreiergruppe) ist ein Naked Subset mit 3 Kandidaten. Wenn man in einem Haus drei Zellen findet, in welchen zusammen nur 3 verschiedene Kandidaten (3-er Subset) vorkommen, können diese Kandidaten aus den anderen Zellen des selben Hauses gelöscht werden.

Zahlen-Gitter
Naked Triple

Kandidaten-Gitter
Naked Triple Kandidaten-Gitter

Code: 390000700 000000650 507000349 049380506 601054983 853000400 900800134 002940865 400000297 [1]

In diesem Beispiel gibt es in der orangen Box drei Zellen, in denen nur die grün markierten Kandidaten 126 stehen. Damit jede der 3 Zellen einen der 3 Kandidaten abbekommt, darf keine der 3 Zahlen 126 in einer andere Zelle der orangen Box stehen. Die rot markierten Kandidaten können daher gelöscht werden.

In der gelben Zelle bleibt damit nur noch der Kandidat 8 übrig. Es kann also im nächsten Schritt die Zahl 8 in die gelbe Zelle gesetzt werden.

Beispiel Naked Triple in Spalte

Zahlen-Gitter
Naked Triple

Kandidaten-Gitter
Naked Triple Kandidaten-Gitter

Code: 000294380 000178640 480356100 004837501 000415700 500629834 953782416 126543978 040961253 [2]

In diesem Beipsiel teilen sich die grün markierten Kandiaten 369 genau drei Zellen der orangen Spalte. In diesen Zellen kommen keine anderen Kandidaten vor. Die Kandidaten 369 bilden somit ein 3-er Subset. Damit jede dieser 3 Zellen einen der 3 Kandidaten abbekommt, darf keine der 3 Zahlen 369 in einer anderen Zelle der orangen Spalte stehen. Der rot markierte Kandidat kann also gelöscht werden.

Dieses Beispiel zeigt, dass nicht in jeder der 3 Zellen mit den grün markierten Kandidaten jeder Kandidat vorkommen muss. Trotzdem bilden die 3 grünen Kandidaten ein 3-er Subset, weil in diesen Zellen keine anderen Kandidaten als diese 3 vorkommen.

Beispiel Locked Triple

Wenn sich ein Naked Triple auf eine Zeile oder Spalte und gleichzeitig auf eine Box beschränken, spricht man von einem Locked Triple. In diesem Fall können Kandidaten sowohl aus der Zeile oder Spalte, als auch aus der Box gelöscht werden. Die Methode Locked Triple funktioniert ähnlich wie die Kombination Locked Candidates Box/Line und Line/Box und mit 3 Kandidaten gleichzeitig, ist also sehr effizient.

Die Sudoku-App behandelt die Methode Locked Triple als zwei separate Methoden Naked Triple, einmal angewandt auf die Box und einmal auf die Zeile oder Spalte.

Kandidaten-Gitter
Locked Triple Kandidaten-Gitter

Kandidaten-Gitter
Locked Triple Kandidaten-Gitter

Code: 400500370 320000004 060000000 800002030 210840000 000000090 070090100 940651000 000070000 [3]

In diesem Beispiel kommen die 3 grünen Kandidaten 567 als 3-er Subset in den Zellen der orangen Box (links) und der orangen Zeile (rechts) vor. Damit jede dieser 3 Zellen einen der 3 Kandidaten 567 abbekommt, darf keine der 3 Zahlen 567 in einer anderen Zelle derselben Box und derselben Zeile stehen. Somit können die rot markierten Kandidaten alle gelöscht werden.

Beispiel Naked Quadruple

Naked Quadruples (Nakte Vierergruppe) funktionieren gleich wie Naked Triples und Naked Pairs, nur werden jetzt vier Kandidaten in vier Zellen benötigt.

Zahlen-Gitter
Naked Quadruple

Kandidaten-Gitter
Naked Quadruple Kandidaten-Gitter

Code: 010720563 056030247 732546189 693287415 247615938 581394000 000002000 000000001 005870000 [4]

Dieses Beispiel zeigt, dass Naked Quadruples vor allem dann relativ schwer zu entdecken sind, wenn nicht alle 4 Kandidaten in jeder Zelle vorkommen. Das 4-er Subset besteht hier aus den Kandidaten 3489. In jeder Zelle mit den grün markierten Kandidaten kommen ausser den Kandidaten dieses Subsets keine anderen Kandidaten vor. 4 Zellen mit Kandidaten eines 4-er Subsets bilden damit ein Naked Quadruple.

Damit jede dieser 4 Zellen einen der 4 Kandidaten 3489 abbekommt, darf keine der 4 Zahlen 3489 in einer anderen Zelle der orangen Zeile stehen. Somit können die rot markierten Kandidaten gelöscht werden.

Beispiel Naked N-Tuple

Höhere Naked Subsets mit mehr als 4 Kandidaten kommen selten vor. Das Prinzip ist immer dasselbe. Nachfolgend ein Beispiel eines Naked 5-Tuple:

Zahlen-Gitter
Naked 5-Tuple

Kandidaten-Gitter
Naked 5-Tuple Kandidaten-Gitter

Code: (1578)(14578)(13478)(25)(6789)(16789)(123679)(12369)(1237) 9(157)(137)(25)(67)(167)(12367)84 (178)623(4789)(14789)(179)5(17) (1278)(12789)(1789)6(2378)(378)(12389)45 3(25789)(789)41(578)(289)(29)6 (12568)(12458)(1468)9(2358)(358)(1238)7(1238) (2678)(2789)(6789)1(34569)(34569)(2345678)(236)(2378) 4(189)57(369)2(1368)(136)(138) (1267)3(167)8(456)(456)(124567)(126)9

In der Box 9 kommt das 5-er Subset mit den grün markierten Kandidaten 12368 in 5 Zellen vor. Damit jede dieser Zellen einen der Kandidaten 12368 abbekommt, darf keine der 5 Zahlen des 5-er Subsets in einer anderen Zelle der Box 9 vorkommen. Die rot markierten Kandidaten des Subsets können somit gelöscht werden. In der gelben Zelle bleibt dabei nur noch die 7 übrig, womit im nächsten Schritt die Zahl 7 in die gelbe Zelle gesetzt werden kann.

Weitere Beispiele mit Naked Subsets

Quellen

hodoku.sourceforge.net
http://hodoku.sourceforge.net/de/show_example.php?file=n302&tech=Naked+Triple
hodoku.sourceforge.net
http://hodoku.sourceforge.net/de/show_example.php?file=n301&tech=Naked+Triple
hodoku.sourceforge.net
http://hodoku.sourceforge.net/de/show_example.php?file=l302&tech=Locked+Triple
hodoku.sourceforge.net
http://hodoku.sourceforge.net/de/show_example.php?file=n401&tech=Naked+Quadruple
Weitere Infos zur Seite
Erzeugt Sonntag, 17. Februar 2013
von wabis
Zum Seitenanfang
Geändert Sonntag, 6. Dezember 2015
von wabis