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.