email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Formacja-XY (XY-Wing)

W skład Formacji-XY (ang. XY-Wing) wchodzą trzy komórki, których zwajemne położenie przypomina literę "Y", dlatego też niekiedy metodę tą nazywamy formacją-Y (ang. Y-Wing). Komórki, które wchądzą w skład formacji-XY muszą spełniać następujące warunki:

  • komórki wchodzące w skład formacji-XY składają się z dwóch kandydatów
  • Pierwsza komórka (tzw. macierzysta) składa się z dwóch wartości, które oznaczymy symbolicznie przez "X" i "Y"
  • Druga komórka (pierwsza gałąź) o wartościach "X" i "Z" leży na tej samej linii (wiersz/kolumna) bądź w tym samym bloku 3x3 co komórka macierzysta
  • Trzecia komórka (druga gałąź) o wartościach "Y" i "Z" leży w tym samym bloku 3x3 bądź w tej samej linii co komórka macierzysta
  • te trzy komórki nie mogą należej do jednej linii bądź jednego bloku 3x3 (gdyby tak było mielibyśmy odkrytą trójkę w linii lub w bloku: {XY} {XZ} {YZ})
  • Niech usuwalne komórki dla danej pozycji jest zbiórem wszystkich komórek, które leżą w tym wierszu, kolumnie lub bloku 3x3 co dana komórka oprócz tej komórki. Jeśli są spełnione powyższe warunki wówczas wartość "Z" możemy usunąć z tych wszystkich pozycji, które należą jednocześnie do usuwalnych komórek obydwu gałęzi formacji-XY

Zapis powyższy jest w miarę precyzyjny przez to jest jednak ciężki do zrozumienia, dlatego postaram się zobrazować się formację-XY na przykładach.

Formacja-XY (pierwszy wariant)

W tym wariańcie jedna komórka gałąź znajduje się w tym samym bloku co komórka macierzysta, a druga komórka gałąź znajduje się na tej samej linii (wiersz/kolumna) co komórka macierzysta.

spójrz na zadanie sudoku na diagram obok.

Aby Analiza formacji-XY stała się jaśniejsza zostawiliśmy tylko trzy komórki należące do formacji pomijając zawartości innych komórek. Komórką macierzystą formacji jest komórka [1,1] o wartościach X=8 i Y=9. Pierwsza komórka gałąź jest komórka [2,3] o wartościach Y=9 i Z=2, a druga to komórka [4,1] o wartościach X=8 i Z=2. Na diagramach poniżej zobaczymy jak działa ta formacja w zależności od przyjmowanej wartości w komórce macierzystej.

Załóżmy, że komórka macierzysta [1,1] przyjmuje wartość X=8, wówczas komórka gałąź [4,1] będzie miała wartość Z=2, wówczas wszystkie szare komórki na diagramie nie będą mogły przyjąc wartości Z=2 (te wszystkie szare komórki to komórki usuwalne punktu [4,1]).

Załóżmy, że komórka macierzysta [1,1] przyjmuje wartość Y=9, wówczas inna komórka gałąź [2,3] będzie miała wartość Z=2, wówczas wszystkie szare komórki na diagramie nie będą mogły przyjąc wartości Z=2 (szare komórki to usuwalne komórki punktu [2,3]).

Widzimy zatem, że niezależnie od tego jakie wartości przyjmie komórka macierzysta, wartość Z=2 nie będzie mogła wystąpić w tych szarych komórkach, gdyż są to wspólne komórki z powyższych dwóch diagramów (te szare komórki to część wspólna usuwalnych komórek czyli punkty: [4,1] i [2,3]).

Analizując jeszcze raz:
-> załóżmy, że komórka macierzysta [1,1] przyjmuje wartość X=8, wówczas komórka [4,1] przyjmie wartość Z=2. W tym przypadku komórki [2,1] [3,1] [4,3] [5,3] [6,3] nie będą mogły przyjąc wartości Z=2 (wyszczególnione szare komórki).
-> zakładając z kolei, że komórka [1,1] przyjmie wartość Y=9, wówczas komórka [2,3] przyjmie wartość Z=2. W tym przypadku, te same komórki co poprzednio, a więc: [2,1] [3,1] [4,3] [5,3] [6,3] nie będą mogły przyjąc wartości Z=2.
-> Tak więc niezależnie od przyjmowanej wartości w komórce macierzystej wartość Z=2 nie może wystąpić w tych szarych polach, czyli możemy usunąć wartość Z=2 z tych szarych pól!

W naszym przypadku możemy usunąć wartość Z=2 z komórek [3,1] i [4,3].

Formacja-XY (drugi wariant)

W tym wariańcie jedna komórka gałąź znajduje się w tym samym wierszu co komórka macierzysta, a druga komórka gałąź znajduje się w tej samej kolumnie co komórka macierzysta, oraz żadna z komórek gałęzi nie znajduje się w tym samym bloku 3x3 co komórka macierzysta.

W tym przypadku komórka macierzysta to komórka [1,1] o wartościach X=2 i Y=3, pierwsza komórka gałąź to komórka [1,8] o wartościach Y=3 i Z=7, a druga komórka gałąź to komórka [5,1] o wartościach X=2 i Z=7.

Analizując podobnie jak pierwszy wariant dojdziemy do wniosku, że jedyną komórką wspólną dla obydwu usuwalnych komórek punktów gałęzi to punkt [5,8].

Rozpatrzmy ten przykład formacji-XY:
-> załóżmy, że komórka macierzysta [1,1] przyjmuje wartość "2", wówczas komórka [5,1] przyjmie wartość "7". W tym przypadku komórka [5,8] nie będzie mogła przyjąć wartości "7" lub inaczej wartość "7" możemy usunąc z komórki [5,8].
-> zakładając z kolei, że komórka [1,1] przyjmie wartość "3", wówczas komórka [1,8] przyjmie wartość "7". W tym przypadku, ta same komórka co poprzednio, a więc [5,8] nie będzie mogła przyjąc wartości "7". Tak więc możemy usunąć wartość "7" z komórki [5,8].