Sudoku Löser

Extrem

Region Forcing Chain

Eine fortgeschrittene Ketten-Technik, die alle möglichen Positionen eines Kandidaten in einer Region untersucht, um einen Ausschluss oder eine Platzierung zu beweisen.

Eine Region Forcing Chain (auf Deutsch auch "Erzwingende Regionenkette" genannt) ist eine sehr komplexe logische Technik, die eingesetzt wird, wenn einfachere Strategien ihr Potenzial ausgeschöpft haben. Sie beruht auf einer ganz grundlegenden Sudoku-Regel: Ein Kandidat muss exakt einmal in jeder Region (Reihe, Spalte oder 3x3-Block) platziert werden.

Indem man die Konsequenzen (die logischen Ketten) von jeder möglichen Position eines Kandidaten in einer Region nachverfolgt, stellt man manchmal fest, dass alle möglichen Ausgangspositionen zur exakt gleichen Schlussfolgerung über ein anderes Feld führen. Wenn jedes mögliche Szenario zu demselben Ergebnis führt, dann muss dieses Ergebnis wahr sein!

Interaktives Beispiel

1 2 3 4 5 6 7 8 9
3
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
5
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
8
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1
1 2 3 4 5 6 7 8 9
3
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9
1
1 2 3 4 5 6 7 8 9
4
1 2 3 4 5 6 7 8 9
6
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
5
1 2 3 4 5 6 7 8 9
3
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
6
1 2 3 4 5 6 7 8 9
7
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9
1
1 2 3 4 5 6 7 8 9
3
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
8
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
6
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
5
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
2
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
8
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
3
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
7
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
2
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
5
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9

Klicken Sie auf "Logik anwenden", um die Strategie in Aktion zu sehen.

Erklärung des echten Beispiels

Im obigen Beispiel hat unser Solver eine Region Forcing Chain angewendet, um den Kandidaten 7 aus R2C8 zu eliminieren.

Schauen wir uns die Ausgangssituation an: Die Ziffer 2 in Reihe 1 ist auf genau drei Felder beschränkt: R1C1, R1C4 und R1C7. Da es eine Sudoku-Regel ist, dass jede Reihe genau eine 2 haben muss, wissen wir, dass ines dieser Felder zwingend eine 2 sein muss. Wir wissen nur noch nicht welches! Lassen Sie uns die Ketten für jede der drei Möglichkeiten durchspielen:

  1. Was passiert, wenn R1C1 = 2 ist?
    • Dies erzwingt, dass R2C3 nicht 2 ist (da sie sich Block 1 teilen).
    • Wenn R2C3 keine 2 ist, muss es eine 7 sein (es ist ein Feld mit nur zwei Kandidaten: {2, 7}).
    • Wenn R2C3 = 7 ist, dann kann R2C8 keine 7 sein (da sie sich Reihe 2 teilen).
  2. Was passiert, wenn R1C4 = 2 ist?
    • (Der Solver hat eine ähnliche Kette gefunden, die von diesem Startpunkt aus beweist, dass R2C8 keine 7 sein kann).
  3. Was passiert, wenn R1C7 = 2 ist?
    • (Der Solver hat eine weitere Kette gefunden, die von diesem Startpunkt aus beweist, dass R2C8 keine 7 sein kann).

Da alle drei möglichen Positionen für die 2 in Reihe 1 zu der unvermeidlichen Schlussfolgerung führen, dass R2C8 keine 7 sein kann, können wir die 7 vertrauensvoll aus R2C8 löschen. Wir müssen gar nicht wissen, wo die 2 in Reihe 1 tatsächlich hingehört, um zu wissen, dass R2C8 definitiv keine 7 ist!

Wie es funktioniert

  1. Eine Region & einen Kandidaten finden: Suchen Sie nach einer Reihe, Spalte oder einem Block, in der ein bestimmter Kandidat (z. B. 2) auf eine kleine Anzahl von Feldern beschränkt ist (normalerweise zwei oder drei).
  2. Jedes Szenario untersuchen: Stellen Sie sich für jedes dieser in Frage kommenden Felder vor, Sie würden den Kandidaten dort platzieren. Was erzwingt das im Rest des Gitters? Folgen Sie den logischen Ketten (unter Verwendung starker und schwacher Verbindungen).
  3. Die gemeinsame Schlussfolgerung finden: Wenn alle dieser separaten Ketten schließlich zum gleichen Ergebnis für ein bestimmtes Zielfeld führen, haben Sie eine Region Forcing Chain gefunden!

Arten von Ergebnissen

  • Ausschluss (Elimination - RFE): Alle Zweige beweisen, dass ein Zielfeld einen bestimmten Kandidaten nicht enthalten kann. Sie können diesen Kandidaten sicher eliminieren.
  • Platzierung (Placement - RFP): Alle Zweige beweisen, dass ein Zielfeld einen bestimmten Kandidaten enthalten muss. Sie können diesen Kandidaten sofort platzieren.

Wann man Forcing Chains einsetzt

Forcing Chains (Erzwingende Ketten) sind extrem mächtig, aber auch rechnerisch und mental sehr anspruchsvoll. Sie erfordern umfangreiches "Was-wäre-wenn"-Denken oder Ausprobieren (Trial-and-Error). Aus diesem Grund werden sie von menschlichen Lösern im Allgemeinen als Techniken des letzten Auswegs betrachtet, die erst eingesetzt werden, wenn alle fortgeschrittenen, musterbasierten Strategien (wie z. B. Alternating Inference Chains oder 3D Medusa) fehlgeschlagen sind.

Verwandte Strategien

  • Alternating Inference Chain (AIC): Eine einzelne Kette, die einen Ausschluss beweist, ohne dass mehrere Startpunkte getestet werden müssen.
  • Cell Forcing Chain: Ähnlich wie eine Region Forcing Chain, aber anstatt alle Positionen für einen Kandidaten in einer Region zu testen, testen Sie hier alle möglichen Kandidaten für ein einzelnes Feld.
  • 3D Medusa: Eine fortgeschrittene Färbetechnik, welche manchmal dieselben Schlüsse ziehen kann, ohne explizit mehrere Zweige zu untersuchen.