Wskazówki

Technika XY-Chain: Wnioskowanie łańcuchowe z komórkami dwuwartościowymi

2025-06-05 · 10 min czytania
Baza Wiedzy / Indeks Technik / XY-Chain

XY-Chain jest potężną metodą wnioskowania łańcuchowego wśród zaawansowanych technik Sudoku. Jest rozszerzeniem XY-Wing, wykorzystującym struktury łańcuchowe tworzone przez wiele komórek dwuwartościowych (komórek z tylko dwoma kandydatami) do eliminacji kandydatów.

Podstawowa zasada:
XY-Chain składa się z serii komórek dwuwartościowych, gdzie sąsiednie komórki dzielą jednego kandydata. Początek i koniec łańcucha mają każdy kandydata nie dzielonego. Jeśli te dwie liczby są takie same (nazywane Z), to komórki, które widzą zarówno początek, jak i koniec łańcucha, mogą wyeliminować kandydata Z. Ponieważ: podążając za logiką łańcucha, Z musi pojawić się na początku lub końcu łańcucha.
Animacja Zasady XY-Chain
Zasada XY-Chain: Start{Z,A} i Koniec{C,Z} dzielą kandydata Z, Z musi być na Start lub Koniec, eliminuj Z ze wspólnego widocznego obszaru

Przed przeczytaniem tego artykułu zaleca się zrozumienie konwencji nazewnictwa Sudoku, Par nagich i podstaw XY-Wing.

Struktura XY-Chain

XY-Chain zawiera następujące kluczowe elementy:

  • Węzły łańcucha: Każdy węzeł to komórka dwuwartościowa {A,B}
  • Połączenia łańcucha: Sąsiednie węzły muszą się „widzieć" (ten sam wiersz, kolumna lub blok) i dzielić jednego kandydata
  • Początek i koniec łańcucha: Każdy ma kandydata nie dzielonego z sąsiednim węzłem
  • Warunek eliminacji: Gdy kandydaci nie dzieleni początku i końca są tacy sami, eliminacja jest możliwa

Notacja łańcucha: A(x,y) → B(y,z) → C(z,w) → ... gdzie nawiasy zawierają kandydatów, strzałki pokazują kierunek łańcucha, a sąsiednie węzły dzielą jedną liczbę (jak y, z).

Dlaczego XY-Chain działa?

1 Propagacja łańcucha: Załóżmy, że łańcuch to A{X,Y} → B{Y,Z} → C{Z,W}. Jeśli A=X, to B musi =Z (ponieważ B nie może =Y), potem C musi =W (ponieważ C nie może =Z).
2 Dwie możliwości: Początek łańcucha ma dwóch kandydatów {P,Q}, gdzie Q jest dzielony z następnym węzłem. Jeśli początek=P, wnioskowanie kończy się; jeśli początek=Q, logika propaguje się wzdłuż łańcucha do końca.
3 Kluczowy wniosek: Jeśli nie dzielona liczba P początku łańcucha równa się nie dzielonej liczbie końca, to P musi pojawić się na początku lub końcu łańcucha.
4 Cel eliminacji: Komórki, które widzą zarówno początek, jak i koniec łańcucha, nie mogą zawierać P (ponieważ P musi być na początku lub końcu).

Przykład 1: XY-Chain 4-węzłowy

Spójrzmy na prosty przykład 4-węzłowego XY-Chain.

Przykład XY-Chain 1
Rysunek 1: XY-Chain R2C2{3,7} → R2C6{3,5} → R9C6{2,5} → R9C7{2,7}, może wyeliminować 7 z R2C7
Otwórz ten przykład w solverze

Proces analizy

1 Identyfikuj węzły łańcucha:
  • R2C2: kandydaci {3, 7} (początek łańcucha)
  • R2C6: kandydaci {3, 5}
  • R9C6: kandydaci {2, 5}
  • R9C7: kandydaci {2, 7} (koniec łańcucha)
2 Weryfikuj połączenia łańcucha:
  • R2C2 i R2C6 są w tym samym wierszu (Wiersz 2), dzielą kandydata 3
  • R2C6 i R9C6 są w tej samej kolumnie (Kolumna 6), dzielą kandydata 5
  • R9C6 i R9C7 są w tym samym wierszu (Wiersz 9), dzielą kandydata 2
3 Określ liczbę do eliminacji:
  • Nie dzielona liczba początku R2C2{3,7} = 7 (3 jest dzielony z R2C6)
  • Nie dzielona liczba końca R9C7{2,7} = 7 (2 jest dzielony z R9C6)
  • Są takie same! Z = 7
4 Proces wnioskowania:
  • Jeśli R2C2=7 → 7 jest na początku łańcucha
  • Jeśli R2C2=3 → R2C6 nie może być 3 → R2C6=5 → R9C6 nie może być 5 → R9C6=2 → R9C7 nie może być 2 → R9C7=7 → 7 jest na końcu łańcucha
  • W obu przypadkach 7 musi być w R2C2 lub R9C7
5 Znajdź cel eliminacji: R2C7 może widzieć zarówno początek łańcucha R2C2 (ten sam wiersz), jak i koniec łańcucha R9C7 (ta sama kolumna).
Wniosek:
XY-Chain: R2C2{3,7} → R2C6{3,5} → R9C6{2,5} → R9C7{2,7}
Może wyeliminować kandydata 7 z R2C7.

Przykład 2: Długi łańcuch 10-węzłowy

XY-Chain może być bardzo długi. Oto przykład 10-węzłowy demonstrujący potężną zdolność wnioskowania łańcuchowego.

Przykład XY-Chain 2
Rysunek 2: XY-Chain R2C5{1,5} → R2C1{1,5} → R1C1{5,8} → R1C7{7,8} → R3C7{7,8} → R3C2{4,8} → R7C2{4,8} → R8C1{4,8} → R8C7{4,9} → R8C3{5,9}, może wyeliminować 5 z R8C5
Otwórz ten przykład w solverze

Proces analizy

1 Identyfikuj węzły łańcucha (10 węzłów):
  • R2C5: {1, 5} (początek łańcucha)
  • R2C1: {1, 5}
  • R1C1: {5, 8}
  • R1C7: {7, 8}
  • R3C7: {7, 8}
  • R3C2: {4, 8}
  • R7C2: {4, 8}
  • R8C1: {4, 8}
  • R8C7: {4, 9}
  • R8C3: {5, 9} (koniec łańcucha)
2 Weryfikuj połączenia łańcucha:
  • R2C5 → R2C1: ten sam wiersz, dzielą 1 (lub 5)
  • R2C1 → R1C1: ta sama kolumna, dzielą 5
  • R1C1 → R1C7: ten sam wiersz, dzielą 8
  • R1C7 → R3C7: ta sama kolumna, dzielą 7 (lub 8)
  • R3C7 → R3C2: ten sam wiersz, dzielą 8
  • R3C2 → R7C2: ta sama kolumna, dzielą 4 (lub 8)
  • R7C2 → R8C1: ten sam blok, dzielą 8
  • R8C1 → R8C7: ten sam wiersz, dzielą 4
  • R8C7 → R8C3: ten sam wiersz, dzielą 9
3 Określ liczbę do eliminacji:
  • Nie dzielona liczba początku R2C5{1,5} = 5 (1 jest dzielony z R2C1)
  • Nie dzielona liczba końca R8C3{5,9} = 5 (9 jest dzielony z R8C7)
  • Są takie same! Z = 5
4 Wniosek: Niezależnie czy początek łańcucha R2C5 to 1 czy 5, kandydat 5 musi pojawić się na początku łańcucha R2C5 lub na końcu łańcucha R8C3.
5 Znajdź cel eliminacji: R8C5 może widzieć zarówno początek łańcucha R2C5 (ta sama kolumna), jak i koniec łańcucha R8C3 (ten sam wiersz).
Wniosek:
XY-Chain (10 węzłów): R2C5 → R2C1 → R1C1 → R1C7 → R3C7 → R3C2 → R7C2 → R8C1 → R8C7 → R8C3
Może wyeliminować kandydata 5 z R8C5.

Jak znaleźć XY-Chain?

Znajdowanie XY-Chain wymaga systematycznego podejścia:

1 Zaznacz komórki dwuwartościowe: Najpierw zidentyfikuj wszystkie komórki z tylko dwoma kandydatami.
2 Wybierz punkt początkowy: Wybierz komórkę dwuwartościową jako początek łańcucha, zapisz jej dwóch kandydatów {P,Q}.
3 Rozszerz łańcuch: Znajdź komórki dwuwartościowe, które mogą „widzieć" bieżący węzeł i dzielą jednego kandydata jako następny węzeł.
4 Sprawdź warunek zakończenia: Po każdym rozszerzeniu sprawdź, czy nie dzielona liczba końca równa się nie dzielonej liczbie P początku.
5 Znajdź cele eliminacji: Znajdź komórki, które widzą zarówno początek, jak i koniec łańcucha i zawierają P.
Ważne uwagi:
  • Każdy węzeł w łańcuchu musi być komórką dwuwartościową
  • Sąsiednie węzły muszą widzieć się nawzajem (ten sam wiersz, kolumna lub blok)
  • Sąsiednie węzły muszą dzielić jednego kandydata
  • Warunek eliminacji: kandydaci nie dzieleni początku i końca są tacy sami
  • XY-Wing to specjalny przypadek XY-Chain (łańcuch o długości 3)

Związek między XY-Chain a XY-Wing

XY-Wing można postrzegać jako XY-Chain o długości 3:

  • XY-Wing: Pivot{X,Y} → Skrzydło1{X,Z} → Skrzydło2{Y,Z}... itp., to właściwie nie jest standardowa forma łańcucha
  • Rzeczywista relacja: Struktura XY-Wing ma kształt „Y", podczas gdy XY-Chain jest liniowy
  • Wspólny punkt: Oba używają komórek dwuwartościowych do logicznej eliminacji
  • Różnica: XY-Chain wymaga połączenia łańcuchowego, XY-Wing wymaga, aby pivot widział oba skrzydła

Podsumowanie techniki

Kluczowe punkty stosowania XY-Chain:

  • Wymaganie węzła: Wszystkie węzły to komórki dwuwartościowe
  • Wymaganie połączenia: Sąsiednie węzły mogą się widzieć i dzielą jednego kandydata
  • Warunek eliminacji: Kandydaci nie dzieleni początku i końca są tacy sami
  • Cel eliminacji: Dzielony kandydat w komórkach, które widzą zarówno początek, jak i koniec
  • Długość łańcucha: Teoretycznie nieograniczona, dłuższe łańcuchy są trudniejsze do znalezienia, ale potężniejsze
Ćwicz teraz:
Rozpocznij grę w Sudoku i spróbuj użyć XY-Chain do eliminacji! Najpierw znajdź wszystkie komórki dwuwartościowe, następnie spróbuj połączyć je w łańcuch.
XY-Wing Pary nagie Indeks technik