email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

X-Cykle (X-Cycles)

X-Cykle (ang. X-Cycles) to początek dużej rodziny strategii opartej na "łańcuchach" pomagająca przy rozwiązywaniu trudnych zadań sudoku. X-Cykle są podobne do techniki prostego kolorowania tzn. że jest ona używana dla jednej wartości, z tym że używamy tu zarówno połączeń mocnych jak i słabych.

Zdefiniujemy teraz pewne pojęcia, które będą pomocne przy wytłumaczeniu funcjonowania x-cykli:
połączenie mocne - występuje wtedy, gdy w danym sektorze dana wartość "x" może wystąpić tylko w dwóch miejscach (czyli ma dwie kandydujące pozycje w danym sektorze). Znaczy to dosłownie, że jeśli wartość "x" nie wystąpi w pierwszej pozycji to musi wystąpić w drugiej.
połączenie słabe - występuje wtedy, gdy z danego sektora wybieramy dwie pozycje, obydwie kandydują dla wartości "x", ale w danym sektorze kandydujących pozycji dla wartości "x" jest wiecej niż dwie.

Tak więc x-cyklem nazywamy, pewną liczbę połączeń mocnych i słabych dla wartości "x" połączonych ze sobą w taki sposób, że:
- pierwsze połączenie (mocne lub słabe) łączy się z drugim (tzn. jedna z pozycji należy do pierwszego i drugiego połączenia)
- drugie połączenie łączy się z trzecim, itd.
- ostatnie połączenie łączy się z pierwszym.
Ten zapis stanie się jasny, gdy omówimy go na przykładzie trzech typów x-cykli przedstawionych poniżej.

Wariant 1. Pętla zamknięta o Parzystej liczbie węzłów

Jest to taki x-cykl, w którym każde połączenie mocne jest powiązane z dwoma połączeniami słabymi i analogicznie, każde połączenie słabe jest powiązane z dwoma połączeniami mocnymi. W tym przypadku suma połączeń mocnych i słabych jest parzysta

Na diagramie obok mamy cykl dla wartości "8" czyli 8-cykl. Niech -> oznacza połączenie mocne, a => połączenie słabe zatem nasz 8-cykl możemy zapisać następująco:
[3,2]=>[3,7]->[9,7]=>[8,9]->[8,3]=>[7,2]->[3,2]
czyli mamy po trzy połączenia mocne i słabe, w tym przypadku możemy usunąć wartość "8" z wszystkich pozycji, które leżą w tym samym sektorze co połączenie słabe, ale nie należą do połączenia słabego.
W naszym przypadku możemy usunąć wartość "8" z pozycji: [3,3], [3,9], [7,3], [7,9].

Wariant 2. Pętla zamknięta o Nieparzystej liczbie węzłów

Jest to taki x-cykl, w którym jedno z połączeń mocnych jest powiązane z drugim połączeniem mocnym, reszta połączeń jest regularna, tzn. połączenia mocne są powiązane z połączeniami słabymi i odwrotnie. W tym przypadku suma połączeń mocnych i słabych jest nieparzysta.

Na diagramie obok mamy nieregularny cykl dla wartości "1" czyli 1-cykl, który zapiszemy następująco:
[9,1]->[7,3]=>[5,3]->[5,8]=>[9,8]->[9,1]
czyli mamy po trzy połączenia mocne i dwa słabe, w tym przypadku usuwamy wszystkich kandydatów oprócz wartości "1" z pozycji, która należy do obydwu powiązanych mocnych połączeń.
W naszym przypadku usuwamy wartość "3" i "9" z pozycji [9,1].

Wariant 3. Pętla otwarta o Parzystej liczbie węzłów

Jest x-cyk podobny do 1-szego wariantu z tym, że pętla nie jest zamknięta (pierwszy i ostatni węzeł pętli należą do dwóch różnych pozycji), poza tym jest tak samo jak w wariancie pierwszym, połączenia mocne przeplatane są połączeniami słabymi oraz liczba wezłów jest parzysta. W tym wypadku usuwamy kandydatów o wartości "x" z wszystkich pozycji, które leżą w tym samym sektorze, co pierwszy i ostatni węzeł.

Na diagramie obok mamy otwarty cykl dla wartości "1" czyli 1-cykl, który zapiszemy następująco:
[3,7]->[7,7]=>[7,2]->[8,3]
możemy więc usunąć wartość "1" z tych pozycji, które leżą w tym samym sektorze co pierwsza i ostatnia pozycja cyklu. W naszym przypadku usuwamy wartość "1" z pozycji [3,3].