|
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].
|
|
