email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Naprzemienny Łańcuch Wnioskowania (Alternating Inference Chains)

Naprzemienny Łańcuch Wnioskowania (ang. Alternating Inference Chains [AIC]) rozszerza metodę X-Cykle na nowy wymiar. X-Cykle są związane z jednym wartością kandydata natomiast AIC używa kandydatów o dowolnych wartościach. Mianowicie możemy łączyć dwóch kandydatów w sektorze (wiersz/kolumna/blok 3x3) o tej samej wartości (bi-lokalizacja) oraz dwóch różnych kandydatów w tej samej komórce (bi-wartość). AIC podobnie jak X-Cykle używa mocnych i słabych połączeń, niemniej określenia te będą trochę inne niż w X-Cyklach. Tworząc łańcuch AIC 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.

Prosty Naprzemienny Łańcuch Wnioskowania (Simple AIC)

połaczenie mocne występuje wtedy, gdy:

  • W danej komórce występują dwie wartości (między dwoma różnymi wartościami)
  • w danym sektorze (wiersz/kolumna/blok 3x3) występują dwie komórki, w których występuje wartość "nVal" (między dwoma pozycjami dla wartości "nVal"). Definicję tą rozszerzę póżniej przy Grupowym AIC.

połaczenie słabe występuje wtedy, gdy:

  • W danej komórce występują więcej niż dwie wartości (między dwoma różnymi wartościami)
  • w danym sektorze (wiersz/kolumna/blok 3x3) występują więcej niż dwie komórki, w których występuje wartość "nVal" (między pozycjami dla wartości "nVal").

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 8-miu węzłach:
[7,6]=5 [8,6]=5 [8,6]=3 [8,5]=3 [4,5]=3 [4,5]=2 [6,6]=2 [7,6]=2 [7,6]=5

Usuwamy kandydatów w następujący sposób:
- jeśli dwa kolejne węzły pętli leżą w tej samej pozycji, to usuwamy z tej pozycji wszystkie wartości oprócz wartości należących do tych węzłów pętli.
- jeśli dwa kolejne węzły pętli leżą w tym samym sektorze (wiersz/kolumna/blok 3x3), czyli mają tą wartość 'nVal' to usuwamy tą wartość ze wszystkich pozycji sektora, do którego należą te dwa węzły oprócz pozycji wezłów pętli.
W naszym przypadku:
- dwa kolejne węzły leżą w tej samej komórce (pozycja [7,6] usuwamy wartość "6", pozycja [8,6] usuwamy wartość "8")
- dwa kolejne węzły leżą w tym samym sektorze (węzły [8,6]=3 i [4,6]=3, usuwamy wartość "3" z 5-tej kolumny czyli z pozycji [2,5] i [6,5] oraz węzły [4,5]=2 i [6,6]=2 usuwamy wartość "2" z 5-ego bloku czyli z pozycji [4,4], [6,4], i [6,5]).

Wariant 2. Pętla zamknięta o Nieparzystej liczbie węzłów
Na diagramie po lewej stronie mamy następującą pętlę o 7-miu węzłach:
[7,6]=4 [7,2]=4 [7,2]=2 [7,8]=2 [9,9]=2 [9,9]=4 [9,6]=4 [7,6]=4

Szukamy takiego węzła pętli, który ma mocne połączenie z poprzednim i następnym węzłem pętli oraz liczba kolejnych mocnych połączeń (aż do słabego połączenia) zarówno od tego węzła wstecz jak i do przodu jest nieparzysta, wówczas usuwamy wszystkie wartości z tej pozycji węzła oprócz wartości, która należy do tego węzła. Wyjaśniam: liczba kolejnych silnych połączeń od wezła [7,6]=4
jedno w przód [7,6]=4 [7,2]=4
pięć wstecz [7,2]=2 [7,8]=2 [9,9]=2 [9,9]=4 [9,6]=4 [7,6]=4
Czyli węzeł [7,6]=4 spełnia warunek wariantu 2-ego zatem usuwamy z komórki [7,4] wszystkie wartości oprócz wartości "4", w naszym przypadku usuwamy wartości "3", "6" i "9".

Wariant 3a. Pętla otwarta o parzystej liczbie węzłów, pierwszy i ostatni węzeł leżą w różnych sektorach (wiersz/kolumna/blok 3x3) ale ma tą samą wartość 'nVal'.
Na diagramie mamy pętlę o 8-miu węzłach:
[1,4]=3 [3,4]=3 [3,4]=9 [7,4]=9 [7,4]=2 [7,2]=2 [4,2]=2 [4,3]=3

Usuwamy kandydatów o wartości 'nVal' z wszystkich pozycji, które należą jednocześnie do sektorów pierwszego i ostatniego węzła i nie należą do pętli AIC. W naszym przypadku usuwamy wartość "3" z pozycji [1,2].

Wariant 3b. Pętla otwarta o parzystej liczbie węzłów, pierwszy i ostatni węzeł leżą w tym samym sektorze (wiersz/kolumna/blok 3x3) ale mają różne wartości.
Na diagramie mamy pętlę o 6-ciu węzłach:
[2,1]=7 [6,1]=7 [6,1]=6 [6,7]=6 [2,7]=6 [2,7]=8

Niech 'nVF' wartość pierwszego wezła, a 'nVL' ostatniego, wówczas usuwamy pierwszej pozycji pętli wartość 'nVL', a z ostatniej wartość 'nVF', o ile wartości te nie należą do pętli AIC.
W naszym przypadku usuwamy wartość "8" z pozycji [2,1].

Zgrupowany Naprzemienny Łańcuch Wnioskowania (Grouped AIC)

połaczenie mocne występuje wtedy, gdy:

  • W danej komórce występują dwie wartości (między dwoma różnymi wartościami)
  • w danym sektorze (wiersz/kolumna/blok 3x3) pewna wartość "nVal" należy dokładnie do dwóch wierszy, kolumn lub bloków 3x3 chociaż pozycji w danym sektorze, w których występuje wartość "nVal" może być więcej niż dwie, jeśli tak jest, to połączenie takie nazywamy zgrupowanym mocnym połączeniem (między dwoma grupami pozycji).

Przykładowy blok 3x3 o początku w punkcie [7,1] i końcu w punkcie [9,3] ma 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 AIC 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]).

połaczenie słabe występuje wtedy, gdy:

  • W danej komórce występują więcej niż dwie wartości (między dwoma różnymi wartościami)
  • w danym sektorze połączenie między pozycjami lub grupami pozycji o wartości "nVal" jest słabe jeśli istnieją pozycje w tym sektorze o wartości "nVal", które nie zostały ujęte w tym połączeniu, zobacz powyższy przykład (między pozycjami dla wartości "nVal").

Wariant 1. Pętla zamknięta o Parzystej liczbie węzłów
Przykładowa pętla na diagramie obok o 10-ciu węzłach:
[4,2]=1 [7,2]=1 [7,7]=1,[7,9]=1 [9,9]=1 [9,9]=2 [9,5]=2 [7,4]=2,[8,4]=2 [6,4]=2 [6,4]=1 [6,3]=1 [4,2]=1
Pozycje [7,7]=1,[7,9]=1 oraz [7,4]=2,[8,4]=2 są zgrupowane.

Usuwamy kandydatów w następujący sposób:
- jeśli dwa kolejne węzły pętli leżą w tej samej pozycji, to usuwamy z tej pozycji wszystkie wartości oprócz wartości należących do tych węzłów pętli.
- jeśli dwa kolejne węzły pętli leżą w tym samym sektorze (wiersz/kolumna/blok 3x3), czyli mają tą wartość 'nVal' to usuwamy tą wartość ze wszystkich pozycji sektora, do którego należą te dwa węzły oprócz pozycji wezłów pętli.
W naszym przypadku:
- dwa kolejne węzły leżą w tej samej komórce (pozycja [6,4] usuwamy wartości "3" i "8", pozycja [9,9] usuwamy wartość "3")
- dwa kolejne węzły leżą w tym samym sektorze (węzły [4,2]=1 i [6,3]=1 leżą w tym samym bloku: usuwamy wartość "1" z pozycji [4,3] i [5,3] oraz węzły [7,4]=2,[8,4]=2 i [9,5]=2 leżą w tym samym bloku: usuwamy wartość "2" z pozycji [7,5] i [7,6]).

Wariant 2. Pętla zamknięta o Nieparzystej liczbie węzłów
Na diagramie mamy pętlę o 9-ciu węzłach:
[5,4]=8 [1,4]=8 [1,8]=8 [1,8]=4 [5,8]=4,[6,8]=4 [5,9]=4 [5,9]=2 [5,5]=2 [5,5]=8 [5,4]=8
Pozycje [5,8]=4,[6,8]=4 są zgrupowane.

Szukamy takiego węzła pętli, który ma mocne połączenie z poprzednim i następnym węzłem pętli oraz liczba kolejnych mocnych połączeń (aż do słabego połączenia) zarówno od tego węzła wstecz jak i do przodu jest nieparzysta, wówczas usuwamy wszystkie wartości z tej pozycji węzła oprócz wartości, która należy do tego węzła.
W naszym przypadku usuwamy wartości "3" i "5" z pozycji [5,4].

Wariant 3a. Pętla otwarta o parzystej liczbie węzłów, pierwszy i ostatni węzeł leżą w różnych sektorach (wiersz/kolumna/blok 3x3) ale ma tą samą wartość 'nVal'.
Na diagramie mamy pętlę o 6-ciu węzłach:
[2,5]=4 [2,5]=1 [2,8]=1 [8,8]=1,[9,8]=1 [9,9]=1 [9,9]=4
Pozycje [8,8]=1,[9,8]=1 są zgrupowane.

Usuwamy kandydatów o wartości 'nVal' z wszystkich pozycji, które należą jednocześnie do sektorów pierwszego i ostatniego węzła i nie należą do pętli AIC. W naszym przypadku usuwamy wartość "4" z pozycji [9,5].

Wariant 3b. Pętla otwarta o parzystej liczbie węzłów, pierwszy i ostatni węzeł leżą w tym samym sektorze (wiersz/kolumna/blok 3x3) ale mają różne wartości.
Na diagramie mamy pętlę o 6-ciu węzłach:
[2,6]=3 [2,6]=8 [1,5]=8 [1,5]=9 [1,8]=9,[1,9]=9 [2,8]=9 [2,8]=6 [2,7]=6
Pozycje [1,8]=9,[1,9]=9 są zgrupowane.

Niech 'nVF' wartość pierwszego wezła, a 'nVL' ostatniego, wówczas usuwamy pierwszej pozycji pętli wartość 'nVL', a z ostatniej wartość 'nVF', o ile wartości te nie należą do pętli AIC.
W naszym przypadku usuwamy wartość "3" z pozycji [2,7].

Naprzemienny Łańcuch Wnioskowania połączony z ALS