Zwingen
Zwingen
Assoziierte Techniken
Ist es Raten? Die Zwingende Ketten-Controverse
Zwingende Ketten sind keine Vermutung, wenn sie als Beweistechnik verwendet werden. Sie untersuchen vorübergehend jeden Zweig von einem gewählten Ausgangspunkt aus, leiten jeden Zweig logisch weiter und behalten nur Schlussfolgerungen, die von jedem Zweig unterstützt werden oder durch einen Widerspruch erzwungen werden.
Der entscheidende Unterschied zur Vermutung ist die Verpflichtung. Eine Vermutung wählt einen Zweig aus und verfährt, als wäre er wahr. Eine Zwangskette vergleicht alle relevanten Zweige vom Ausgangspunkt aus und handelt erst, wenn der Vergleich etwas beweist.
Zwingende Ketten sind weniger elegant als musterbasierte Techniken, aber ihre Schlussfolgerungen sind dann beweisbar korrekt, wenn jeder Zweig korrekt überprüft wurde.
Zelle Zwangskette
Beginnen Sie mit einem Bivalue-Zelle {A, B}. Verfolgen Sie die Implikationen für jede Verzweigung. Vergleichen Sie die Ergebnisse.
Widerspruch: Eine Verzweigung ist ungültig, daher muss der Zelle der andere Kandidat sein.
Konvergenz bei Platzierung: Beide Verzweigungen zwingen dieselbe Ziffer in dasselbe entfernte Zelle.
Konvergenz bei Eliminierung: Beide Verzweigungen eliminieren denselben Kandidaten aus demselben Zelle.
Regionen-Forcing-Kette (Ziffern-Forcing-Kette)
Beginnen Sie mit den 2-3 Positionen einer Ziffer in einer Einheit. Untersuchen Sie jede Position als Zweig. Gleiche drei Ableitungstypen.
Zelle Zwang ist wirksam, wenn Bivalue-Zellen weitreichende Auswirkungen haben. Bereichszwang ist wirksam, wenn die Position einer Ziffer starke kaskadenartige Effekte hat.
Forcing-Netz: Verlängerung der Verzweigungsanzahl
Zelle Forcing Net: Zellen mit 3-6 Kandidaten. Region Forcing Net: Häuser mit 4-6 Positionen für eine Ziffer. Mehr Zweige, teurer, aber kann Ableitungen finden, die Zwingende Ketten nicht kann.
Die Logik ist identisch. Nur die Anzahl der Zweige unterscheidet sich.
Der Propagations-Engine
Jeder Zweig breitet sich durch nackte Einer, versteckte Einer, Gesperrte Kandidaten und nackte Paare aus, iterativ, bis er stabil ist. Eine einzelne Annahme kann sich über Dutzende von Zwischenschritten über das gesamte Feld ausbreiten.
Wenn zwei Zweige über völlig verschiedene Wege zum selben Ergebnis gelangen, beweist die Konvergenz die Sicherheit dieses Ergebnisses.
Die drei Ableitungstypen
Widerspruch: Ein Zweig erzeugt einen ungültigen Zustand. Diese Annahme ist falsch. Am häufigsten.
Konvergenz bei Platzierung: Alle Zweige zwingen die gleiche Ziffer in dasselbe Zelle. Seltener, aber entscheidend.
Konvergenz bei Eliminierung: Alle Zweige eliminieren denselben Kandidaten aus demselben Zelle. Subtilste Art.
Wann sollten Forcing-Techniken eingesetzt werden
Letzte logische Möglichkeit. Wird angewendet, nachdem Muster-basierte Techniken und saubere Ketten fehlschlagen.
Zwingende Ketten mit 2-3 Verzweigungen werden zuerst versucht. Forcing Nets mit 3-6 Verzweigungen sind kostspieliger und werden meist später verwendet. Beide sind Stufe 12 (extrem).
Für Computerlöser ist begrenztes Forcing ein leistungsfähiges Beweismittel, aber nicht automatisch vollständig. Vollständigkeit entsteht erst, wenn die Suche weit genug ausgedehnt wird, um die notwendigen Annahmen abzudecken, was sich der erschöpfenden Rückverfolgung annähert. In der Praxis ist Forcing am besten als kontrollierte logische Suche beschrieben, nicht als Garantie, dass ein fester Tiefensuch-Solver jedes gültige Rätsel lösen kann.
Ein philosophischer Hinweis zur Eleganz und Vollständigkeit
Musterbasierte Techniken zeigen strukturelle Beziehungen auf und sind eleganter. Es gibt jedoch gültige Rätsel, die Logik auf Forcing-Ebene erfordern. Forcing-Techniken sind die Sicherung, die jedes Rätsel fängt, das musterbasierte Techniken nicht bewältigen können.
Der befriedigendste Ansatz: Probieren Sie zunächst alle musterbasierten Techniken aus, und greifen Sie erst dann auf Forcing zurück, wenn das Rätsel dies wirklich erfordert.
Zusammenfassung
Zwingende Ketten und Forcing-Netze sind unter den mächtigsten logischen Techniken, auf Stufe 12 (extrem). Sie untersuchen jeden Zweig von einem gewählten Startpunkt aus, propagieren die Folgen und vergleichen die Ergebnisse. Schlussfolgerungen ergeben sich durch Widerspruch, Konvergenz bei der Platzierung oder Konvergenz bei der Eliminierung. Sie sind die letzte Möglichkeit vor der rohen Rückverfolgung; wenn sie ohne praktische Grenzen ausgeweitet werden, werden sie zu einem vollständigen Suchbeweis, doch begrenzte, menschenähnliche Forcing-Techniken bleiben eine gezielte fortgeschrittene Methode.
Assoziierte Techniken