email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Łańcuch XY (XY-Chain)

Łańcuch XY (ang. XY-Chain) rozpatrywany jest dla pól, które mają dwie kandydujące wartości. Polega ona kolejno na wykonywanych krokach:

  • Wybieramy dowolną pozycję, która posiada dwie kandydujące wartości (nazwiemy ją pozycją startową łańcucha XY), przy czym jednego kandydata oznaczymy jako "x", a drugiego jako "y".
  • Ustalamy, że pozycja startowa przyjmuje wartość "y". Następnie szukamy w sektorach (wiersz/kolumna/blok 3x3) należących do pozycji startowej takiej pozycji, która ma dwóch kandydatów przy czym jeden ma wartość "y", siłą rzeczy jeśli pozycja startowa ma wartość "y" to znaleziona pozycja nie może przyjąć wartość "y", czyli musi przyjąc drugą wartość znalezionej pozycji. Zatem pozycja startowa przyjmująca wartość "y" wymusza aby inna pozycja z jej sektora przyjęła jakąś inną wartość.
  • teraz z kolei aktualna pozycja, w której wymuszono przyjęcie jakiejś wartości wymusza przyjęcie w innej pozycji z dwoma kandydatami jakiejś innej wartości.
  • kroki te powtarzamy dotąd, aż jakaś pozycja przyjmie wartość "x" (pozycję tą nazwiemy pozycją końcową łańcucha XY.
  • Mając tak utworzony łańcuch XY kandydata "x" możemy usunąc z tych pozycji, które:
    • leżą w tym samym sektorze (wiersz/kolumna/blok 3x3) co pozycja startowa i końcowa łańcucha XY
    • pozycja ta leży na przecięciu sektorów (wiersz/kolumna/blok 3x3) pozycji startowej i końcowej łańcucha XY

Przy opisie algorytmu łańcucha XY przeszedłem chyba samego siebie. pewnie gdy będę to któregoś dnia próbował pojąć to będzie ciężko. Mówiąc poważnie jak zwykle wszystko stanie się jasne, gdy przedstawię działanie algorytmu na przykładach.

Pierwszy przykład łańcucha XY:
Pozycja startowa [4,1] ma kandydatów "4" i "5", zakładając, że pozycja startowa przyjmie wartość "4" spowoduje to, że pozycja [8,1] przyjmie wartość "3", to z kolei wymusi by pozycja [8,3] przyjeła wartość "6", a na koniec pozycja [8,9] przyjmie wartość "5".
Czyli otrzymaliśmy łańcuch XY: [4,1]=4→ [8,1]=3→ [8,3]=6→ [8,9]=5
pozycja startowa może przyjąć wartość "5" badź "4", przy czym jeśli przyjmie wartość "4" to pozycja kończąca łańcuch XY przyjmie wartość "5" tak więc możemy usunąć wartość "5" z pozycji [4,9] bo leży ona na przeciećiu wiersza przechodzącego przez pozycję startową i kolumny przechodzącej przez pozycję końcową.
Wyjaśnić to można jeszcze w taki sposób, jeśli pozycja [4,1] przyjmie wartość "5" to pozycja [4,9] nie będzie mogła przyjąć wartość "5", a jeśli pozycja [4,1] przyjmie wartość "4" to pozycja kończąca [8,9] przyjmie wartość "5" i w tym przypadku pozycja [4,9] nie może przyjąć wartości "5". Tak więc niezależnie od tego jaką wartość będzie w punkcie startowym [4,1] pozycja [4,9] nie będzie mogła przyjąć wartości "5".

Drugi przykład łańcucha XY:
Pozycja startowa [4,2] ma kandydatów "1" i "4", zakładając, że pozycja startowa przyjmie wartość "4" spowoduje to powstanie następującego łańcucha XY:
[4,2]=4→ [9,2]=6→ [9,8]=5→ [9,5]=4→ [8,6]=5→ [8,9]=6→ [8,3]=3→ [8,1]=4→ [4,1]=5→ [4,8]=3→ [5,8]=6→ [4,9]=1
W tym przypadku możemy usunąć kandydata "1" z wszystkich pozycji leżących w 4-tym wierszu, gdyż pozycja startowa i końcowa leży w tym wierszu, oczywiście kandydata "1" nie usuwamy z pozycji startowej i końcowej. W naszym przypadku można usunąć wartość "1" z pozycji [4,5].

Porada : Stosując proste kolorowanie powinieneś:

  • nie wykorzystywać głównego diagramu sudoku (kolorując/przekreślając/wymazując znaczniki kandydujących wartości narobiłbyś sobie sporo bałaganu na tym diagramie, który nie zawsze dałoby się doprowadzić do orginalnego wyglądu
  • najlepiej jest wykorzystać do tego kartkę w kratkę i narysować na niej dwa diagramy [9x9] z wyszczególnieniem bloków [3x3]
  • zaczynając kolorowanie dla jakiejś wartości "x" zaznaczamy na obudwu diagramach, wszystkie pozycje zawierające kandydata "x" (można wykorzystać dowolny znak np. kropkę), zaznaczać powinniśmy ołówkiem, gdyż łatwo jest wymazać takie znaki gumką
  • na pierwszym diagramie tworzymy pierwszy łańcuch, a na drugim drugi łańcuch przy czym pozycje ustawione na ON można przykładowo brać w kółko, a pozycje ustawione na OFF przekreślać krzyżykiem.
  • gdy mamy, już utworzone obydwa łańcuchy, na pierwszym diagram zaznaczamy w inny sposób pozycje z drugiego łańcucha, które przyjeły wartość ON przykładowo rysując na tej pozycji trójkąt.
  • mając na jednym diagramie pozycje na ON z obydwu łańcuchów można łatwo zgadnąć z jakich pozycji można usunąć wartość "x"
  • wymazując wszystkie znaki z jednego i drugiego diagramu, można je następnie przygotować do rozpatrywania algorytmu prostego kolorowania dla innej kandydującej wartości