|
Ł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
|
