email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Grupowe X-Cykle (Grouped X-Cycles)

Grupowe X-Cykle (ang. Grouped X-Cycles) to łańcuch dla jakiejś wartości "nVal", który może tworzyć pętlę zamkniętą lub nie. Tworząc łańcuch dla wartości "nVal" po połączeniu mocnym następuje połączenie słabe, a po słabym mocne, z tym, że połączenie słabe może być zastąpione mocnym, ale mocne słabym nie! Czyli jeśli między wezłem nieparzystym a parzystym jest połączenie mocne, to pomiędzy parzystym a nieparzystym może być słabe bądź mocne. Stanie się to jasne na przykładach poniżej, a teraz postaram się rozwinąć pojęcie mocnego połączenia.

połaczenie mocne dla danej wartości "nVal" w pewnym sektorze, występuje wtedy, gdy wszystkie pozycje z tego sektora, które mają kandydata "nVal" należą dokładnie do dwóch innych wierszy, kolumn lub bloków 3x3.

Przykładowo na fragmencie diagramu obok w 9-tym wierszu wartość 4 występuje tylko na dwóch pozycjach. Tu sprawa jest prosta,że między pozycjami [9,6] i [9,9] jest połączenie mocne dla wartości 4.

Przykład kolejny w bloku 3x3 o początku w punkcie [7,1] i końcu w punkcie [9,3] mamy wartość 8 na trzech pozycjach, ale ponieważ wszystkie te pozycje zawierające kandydata 8 występują w dwóch kolumnach 1-szej i 3-ciej to możemy powiedzieć, że między pozycjami [7,1] a [8,3] i [9,3] jest połączenie mocne. Zapisujemy to [7,1] [8,3],[9,3]. Zauważmy, że pozycje [8,3] i [9,3] są zgrupowane i traktujemy je jak jedną pozycję! Stąd nazwa algorytmu Grupowe X-Cykle, czyli jest to algorytm X-Cykle rozszerzony o zgrupowane mocne połączenia. Zauważmy, że między pozycjami [7,1] i [8,3] dla wartości 8 jest połączenie słabe w tym bloku bo pozostaje jeszcze nieuwzględniona pozycja [9,3]. Tak samo jest z połączeniem między pozycjami [7,1] i [9,3] dla wartości 8 (nieuwzględniona pozycja [8,3]).

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

Niech oznacza połączenie mocne, a połączenie słabe

Na przykładzie obok mamy następującą pętlę o 6-ciu węzłach dla wartości 4:
[1,4] [1,9] [9,9] [9,6] [8,5] [2,5],[3,5] [1,4]
Jeśli dwa kolejne węzły tworzą połączenie słabe to usuwamy wszystkich kandydatów o wartości "nVal" należących do tego samego sektora co te dwa węzły, oprócz kandydatów z tych węzłów, w tym przypadku usuwamy wartość 4 z sektorów do których należą pozycje [1,9] i [9,9] czyli z 9-tej kolumny, [9,6] i [8,5] czyli 8-smego bloku oraz [2,5],[3,5] i [1,4] czyli 2-ego bloku Zobacz pozycje zaznaczone na czarno.

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

Na przykładzie obok mamy następującą pętlę o 7-miu węzłach dla wartości 8:
[7,9] [7,1] [8,3],[9,3] [2,3] [1,2] [1,8] [2,9] [7,9]
W tym przypadku szukamy takiego węzła pętli, który ma mocne połączenie z poprzednim i następnym węzłem pętli, wówczas usuwamy wszystkie wartości z tego węzła oprócz wartości "nVal", dla której pętla została utworzona. W naszym przypadku węzeł z pozycji [7,9] ma mocne połączenie z węzłem poprzednim i następnym dla wartości 8, więc możemy usunąć z tego węzła wszystkich kandydatów oprócz wartości 8, czyli usuwamy z pozycji [7,9] wartości {1,6}.

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

Na tym diagramie mamy pętlę otwartą o parzystej liczbie węzłów dla wartości 2 - pierwszy i ostatni węzeł pętli leży w różnych sektorach (wiersz/kolumna/blok 3x3), kolejne węzły tej pętli:
[8,4] [3,4] [3,9] [1,8],[2,8]
Usuwamy kandydatów o wartości 2 z wszystkich pozycji, które leżą w tym samym sektorze, co pierwszy i ostatni węzeł. W naszym przypadku usuwamy wartość 2 z pozycji [8,8].