YouTube
InstagramX-Kette
Schwierigkeit
Beschreibung
Die Technik X-Kette erweitert die Technik "Einfaches Einfärben". Sie benutzt alternierende (sich abwechselnde) starke und schwache Links um Kandidaten zu finden, die eliminiert werden können.
Du weißt nicht, was schwache und starke Links sind? Schau unter Einfaches Einfärben nach einer kurzen Beschreibung.
Beim Einfachen Einfärben hatten wir eine Kette von starken Links bei der wir sagen könnten: "Entweder alle Kandidaten sind korrekt, oder alle Kandidaten sind korrekt."
Jeder Kandidat, der beide Farben sieht (mit ihnen schwach verlinkt ist), kann eliminiert werden.
Bei X-Ketten erlauben wir jedem zweiten Link, ein schwacher Link zu sein.
Die zusätzliche 4 in der Box in der Mitte bewirkt, dass die 4en dort nur per schwachem Link verbunden sind.
Die gleiche logische Schlussfolgerung kann aber immer noch angewendet werden: ein Kandidat, der beide Farben sieht ( und ) kann eliminiert werden.
In diesem Fall kann 4 eliminiert werden.
Warum funktioniert das?
Der Nachteil von schwachen Links ist, dass er weniger Informationen bereitstellt.
Bei einem starken Link wissen wir, dass wenn ein Kandidat falsch ist, der andere wahr sein muss.
Bei einem schwachen Link wissen wir das nicht. Wenn ein Kandidat falsch ist, dann gibt es immer mehr als einen Kandidaten, der wahr sein könnte. (4 bringt hier den Unterschied.)
Und dennoch ist eine Kette aus abwechselnd starken und schwachen Links genauso hilfreich wie eine Kette, die nur aus starken Links besteht.
Aber warum?
Es hilft, sich das ganze aus der Sicht des zu eliminierenden Kandidaten anzuschauen.
Schauen wir uns dieses Beispiel mit einer längeren Kette an.
Wenn 4 korrekt wäre...
... dann wären die 4en falsch...
(weil wir für jede Art von Link wissen, dass wenn ein Kandidat wahr ist, der andere falsch sein muss)
... dann wären die nächsten zwei 4en wieder korrekt...
(weil wir für starke Links wissen, dass, wenn ein Kandidat falsch ist, der andere wahr sein muss)
... und die letzten beiden 4en wären wieder falsch, was natürlich nicht sein darf, weil sie stark miteinander verlinkt sind.
Darum wissen wir, dass der Startkandidat, bei dem wir vorausgesetzt haben, dass er korrekt ist, tatsächlich nicht korrekt ist. Wir können ihn also eliminieren.
Aber nochmal: warum funktioniert unsere Kette mit schwachen Links?
Es liegt daran, wie wir starten. Wir starten immer von unserem Eliminierungskandidaten mit einem schwachen Link, dann stark, dann schwach, etc. (in beide Richtungen)
Da wir mit schwachen Links beginnen, und da wir anfangs annehmen, dass der Eliminierungskandidat korrekt ist, kommen wir bei schwachen Links immer bei einem Kandidaten an, von dem wir auch annehmen, dass er korrekt ist ()."
Und wenn dieser jeweilige Knoten des Links korrekt ist, dann dürfen wir daraus (auch bei einem schwachen Link) schließen dass der andere falsch ist.
Jetzt siehst Du auch, warum es wichtig ist, das die Links sich abwechseln. Wenn nämlich ein schwacher Link an der falschen Position wäre, dann würde das alles so nicht funktionieren.
Starke Links statt schwachen Links
Jetzt wissen wir also, dass schwache Links nicht an jeder beliebigen Stelle in der Kette sein dürfen. Sie dürfen nur an ganz speziellen Positionen (jeder zweiten Stelle) sein. Starke Links dürfen also nicht durch schwache Links ersetzt werden.
Schwache Links können aber immer durch starke Links ersetzte werden, denn schwache Links sagen uns nicht, was uns starke Links nicht auch sagen würden.
Ein starker Link ist ein schwacher Link, aber besser.
Hier die X-Ketten sind also genauso valide, wie die vorigen Beispiele:
Typen der X-Ketten-Technik
Andere Webseiten unterteilen die X-Ketten-Technik in verschiedene Typen. Alle diese Typen können aber reduziert werden auf den einen Typ, der hier auf der Seite beschrieben wird. Das zeige ich für jeden dieser Typen.
Fortlaufende Schöne Schleife
Eine Fortlaufende Schöne Schleife (engl. "Continuous Nice Loop") ist eine Schleife, bei der sich starke und schwache Links perfekt abwechseln. Dort gibt es keine direkt hintereinander liegenden schwachen Links, und direkt hintereinander liegende starke Links gibt es nur, wenn diese den Platz eines schwachen Links einnehmen.
Jede Zelle des Rasters (9) die so einen 9 Kandidaten, als auch einen 9 Kandidaten sieht, kann eliminiert werden.
Warum kann es zu unserer allgemeinen Beschreibung der X-Kette reduziert werden?
Weil wir für jede 9 immer zwei schwache Links haben wir hier. Jetzt sieht es wieder genau wie unsere vorigen Beispiele aus, nicht wahr?
Zwei direkt aufeinander folgenden starken Links
Wenn eine Kette nicht fortlaufend ist, und es zwei aufeinander folgenden starken Links gibt, dann ist 9 die Lösung.
Auch das hier ist nichts anderes als unser allgemeiner Typ, da es als das hier angesehen werden kann (starke Links dürfen schwache Links ersetzen)...
... was zu diesem Versteckten Single führt.