email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Formacja-XYZ (XYZ-Wing)

W skład Formacji-XYZ (ang. XYZ-Wing) przypominającej formację-XY wchodzą trzy komórki, które muszą spełniać następujące warunki:

  • Pierwsza komórka (tzw. macierzysta) składa się z trzech wartości, które oznaczymy symbolicznie przez "X", "Y" i "Z"
  • 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 co komórka macierzysta
  • Trzecia komórka (druga gałąź) o wartościach "Y" i "Z" leży w tym samym bloku 3x3 co komórka macierzysta (jeśli pierwsza komórka gałąź leży na tej samej linii co komórka macierzysta) bądź w tej samej linii co komórka macierzysta (o ile pierwsza komórka gałąź leży w tym samym bloku 3x3 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: {XYZ} {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 wszystkich trzech komórek formacji-XYZ

Zapis powyższy nie jest łatwy do zrozumienia, więc funkcjonowanie tej metody zobrazuję na przykładzie.

spójrz na zadanie sudoku na diagram obok.

Na tym diagramie ujęto tylko komórki należące do formacji-XYZ aby dalsza analiza stała się jaśniejsza. Komórką macierzystą formacji jest komórka [2,1] o wartościach X=4, Y=7 i Z=6. Pierwsza komórka gałąź jest komórka [1,2] o wartościach X=4 i Z=6 leżąca w tym samym bloku 3x3 co komórka macierzysta, a druga komórka gałąź [7,1] o wartościach Y=7 i Z=2 leży w tej samej kolumnie co komórka macierzysta. 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 [2,1] przyjmuje wartość X=4, wówczas komórka gałąź [1,2] będzie miała wartość Z=6, wówczas wszystkie szare komórki na diagramie nie będą mogły przyjąc wartości Z=6 (te wszystkie szare komórki to komórki usuwalne punktu [1,2] tzn. takie, z których należy usunąć kandydata Z=6 o ile komórka [1,2] przyjmie wartość Z=6).

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

Załóżmy teraz, że komórka macierzysta [2,1] przyjmuje wartość Z=6, wówczas komórki zaznaczone kolorem szarym nie będą mogły przyjąć wartości Z=6 (usuwalne komórki punktu [2,1]).

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

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

W naszym przypadku możemy usunąć wartość Z=6 z komórki [3,1].