Sonstiges
Inhaltsverzeichnis
Sue de Coq
Sue de Coq ist eine Variante der Subset Counting-Strategie und wurde von einem Forum-User mit dem Benutzernamen "Sue de Coq" unter dem etwas sperrigen Namen "Two-Sector Disjoint Subsets" (Nicht�berlappende Untermengen in zwei Sektoren) eingef�hrt. Andere Benutzer begannen bald, die Strategie mit dem Benutzernamen des Erfinders "Sue de Coq" (SDC) zu bezeichnen, und dieser Name ist bis heute h�ngen geblieben. Die Strategie in ihrer Standardform ist relativ einfach, aber sie wurde im Lauf der Zeit mehrfach erweitert. Die erweiterten Varianten k�nnen unter Erweiterungen gefunden werden.
Standardform
Die Standardform ist relativ einfach: Man ben�tigt Zellen an der �berschneidung einer Zeile und eines Blocks, und zwar entweder zwei Zellen mit vier Kandidaten oder drei Zellen mit f�nf Kandidaten. Nun sucht man eine zweiwertige Zelle in der Zeile au�erhalb der �berschneidung, deren Kandidaten ganz aus den Kandidaten der �berschneidung genommen sein m�ssen. Eine zweite zweiwertige Zelle muss im Block gefunden werden (auch hier m�ssen die Kandidaten aus der �berschneidung stammen, sie d�rfen auch nicht mit den Kandidaten der Zeilen-Zelle �bereinstimmen).
Diese Konstellation ist ein Sue de Coq: man kann alle Kandidaten der Zeilen-Zelle aus den restlichen Zellen der Zeile l�schen, alle Block-Zellen-Kandidaten aus den restlichen Zellen des Blocks und alle �berschneidungs-Zellen-Kandidaten, die noch nicht an der Reihe waren, aus den restlichen Zellen von Zeile und Block. In Summe ergibt das oft ziemlich beeindruckende Spielz�ge.
In der obigen Definition kann man alle Vorkommen von "Zeile" nat�rlich auch durch "Spalte" ersetzen.
Linkes Beispiel: Die �berschneidungs-Zellen sind r7c13, sie enthalten die Kandidaten {3459}. Die Zeilen-Zelle ist r7c7 (Kandidaten {45}), die Block-Zelle ist r8c3 (Kandidaten {39}). 4 und 5 k�nnen aus dem Rest der Zeile und 3 und 9 k�nnen aus dem Rest des Blocks gel�scht werden.
Betrachtet man die �berschneidung allein, sieht man, dass die Zellen zwei Kandidaten zu viel haben (4 Kandidaten f�r nur 2 Zellen). Da aber die Zeilen-Zelle r7c7 einen dieser Kandidaten enthalten muss, sind es in Wirklichkeit nur noch drei Kandidaten f�r zwei Zellen (3, 9 und 4 oder 5). Die Block-Zelle r8c3 entfernt noch eine M�glichkeit: Die �berschneidungs-Zellen k�nnen jetzt 3 oder 9 und 4 oder 5 sein (2 Kandidaten in zwei Zellen).
Das SDC produziert mehr oder weniger zwei Locked Sets (Gesperrte Mengen): Kandidaten 3 und 9 sind in (r7c13, r8c3) eingesperrt. Da alle diese Zellen in Block 6 sind, k�nnen 3 und 9 in keiner anderen Zelle des Blocks gesetzt werden. Kandidaten 4 und 5 sind in (r7c13, r7c7) eingesperrt. Da alle diese Zellen in der selben Zeile sind, k�nnen 4 und 5 nirgendwo sonst in dieser Zeile vorkommen.
Das rechte Beispiel zeigt eine �berschneidung mit drei Zellen und f�nf Kandidaten: Zellen r789c9 enthalten Kandidaten {24567}. Die Spalten-Zelle r2c9 enth�lt Kandidaten {56}, die Block-Zelle r9c7 enth�lt Kandidaten {27}. Die Logik ist gleich wie oben, aber das Resultat ist drei Kandidaten in drei Zellen: Die �berschneidungszellen k�nnen sein {2 oder 7, 4 und 5 oder 6}. Das bedeutet, dass Kandidat 4 in der �berschneidung eingesperrt ist und daher sowohl aus der Spalte als auch aus dem Block eliminiert werden kann.
Erweiterungen
Sue de Coq kann auf zwei Arten erweitert werden:
- Die �berschneidungs-Zellen k�nnen zus�tzliche Kandidaten enthalten. F�r jeden zus�tzlichen Kandidaten muss eine zus�tzliche Zelle in Zeile/Spalte oder Block gefunden werden.
- Die Zeilen-Zellen (Spalten-Zellen) und Block-Zellen k�nnen Kandidaten haben, die nicht in den �berschneidungs-Zellen vorkommen. F�r jeden solchen Kandidaten muss eine weitere Zelle gefunden werden.
Wichtig ist auch zu beachten, dass nicht alle Zellen an der �berschneidung Block/Zeile (Block/Spalte) wirklich �berschneidungs-Zellen sein m�ssen. Eine eventuelle dritte Zelle kann auch zu den Zeilen- (Spalten-) oder Block-Zellen geh�ren. Au�erdem kann ein Zusatzkandidat, der nicht aus den �berschneidungs-Zellen stammt, in Zeilen- und Block-Zellen gleichzeitig vorkommen.
Eine etwas formalere (und exaktere) Definition aus dem originalen Two-Sector Disjoint Subset Forumsbeitrag:
Wir betrachten eine Menge an nicht gef�llten Zellen C, die in der �berschneidung von Block B und Zeile (oder Spalte) R liegt. Angenommen |C|>=2. V sei die Menge der in C vorkommenden Kandidaten. Angenommen |V|>=|C|+2. Das Muster erfordert, dass |V|-|C|+n Zellen in B und R gefunden werden, mit mindesten einer Zelle in beiden H�usern, mit mindestens |V|-|C| Kandidaten aus V und mit n der Anzahl Kandidaten, die nicht aus V stammen. Die neuen Zellen seien CB und CR und ihre Kandidaten VB und VR. Kein Kandidat aus V darf in VB und VR gleichzeitig auftreten. Dann muss C die Kandidaten V\(VB U VR) (m�glicherweise leer), |VB|-|CB| Elemente aus VB und |VR|-|CR| Elemente aus VR enthalten. Das Konstrukt erlaubt uns, die Kandidaten VB U (V\VR) aus B\(C U CB) und die Kandidaten VR U (V\VB) aus R\(C U CR) zu eliminieren.
Einige Beispiele:
Linke Seite: �berschneidungs-Zellen r46c8 mit Kandidaten {3578}, Spalten-Zelle r8c8 {35} und Block-Zellen r4c7,r5c9 {789}. Das ist praktisch der Standardfall, au�er dass die Block-Zellen Kandidaten 9 enthalten, der nicht aus den �berschneidungs-Zellen stammt. Aus diesem Grund sind auch zwei Block-Zellen n�tig.
Rechte Seite: �berschneidungs-Zellen r456c1 - {123479}. 6 Kandidaten in drei Zellen ist einer zu viel. Eine der beiden anderen Zellen-Mengen muss aus zwei Zellen mit drei Kandidaten bestehen. Im Beispiel sind es die Spalten-Zellen: r89c1 mit {234}. Die Block-Zellen haben einen zus�tzlichen Kandidaten 5, der nicht aus den �berschneidungs-Zellen stammt.
Das linke Beispiel stammt aus dem Player's Forum: Es ist eine normale "4 Kandidaten in zwei Zellen"-Variante, aber beide zus�tzlichen Mengen (Spalten-Zellen und Block-Zellen) enthalten den selben zus�tzlichen Kandidaten (Kandidat 1).
Das rechte Beispiel ist 5 Kandidaten in zwei Zellen und demonstriert eine Kombination aus allen Erweiterungen:
- Obwohl die �berschneidung von Spalte 4 mit Block 2 drei ungel�ste Zellen enth�lt, sind nur zwei von ihnen �berschneidungszellen: r23c4 - {13689}. Zelle r1c4 geh�rt zu den Block-Zellen.
- Spalten-Zelle r5c2 hat zwei Kandidaten {39}, zur G�nze aus den �berschneidungs-Zellen: Das ist normal.
- Jetzt sind aber immer noch zwei Kandidaten zu viel, es werden also zwei Block-Zellen ben�tigt. Leider kann eine passende Menge an Zellen f�r die Kandidaten {168} nur gefunden werden, wenn man Kandidat 7 zus�tzlich dazu nimmt. Es gibt daher drei Block-Zellen: r1c46,r2c6 mit Kandidaten {1678}.
Das resultierende Sue de Coq eliminiert 13 Kandidaten.
Copyright © 2008-12 by Bernhard Hobiger
Alles Material auf dieser Site unterliegt der GNU FDLv1.3.