email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Oddalon Para (Remote Pair)

Zamknięta Para (ang. Locked Pair) ma następujące własności:

  • składa się z dwóch komórek (węzłów).
  • komórki węzły leżą w tym samym sektorze (wiersz/kolumna/blok 3x3).
  • obydwa węzły mają dwie kandydujące wartości. Kandydaci są tacy sami w obydwu węzłach.
  • jeżeli powyższe trzy warunki są spełnione to w sektorze, w którym występuje zamknięta Para, kandydujące wartości z komórek węzłów mogą wystąpić tylko w komórkach węzłach.

Dwie zamknięte pary sa połączone jeśłi istnieje taka komórka węzeł, która należy jednocześnie do pierwsze i drugiej zamkniętej pary. Analogicznie N zamkniętych par jest połączonych jeśli pierwsza zamknięta para jest połączona z drugą, druga z trzecią,..., (N-1) para z N-tą zamkniętą parą.

Oddalona Para (ang. Remote Pair) występuje wtedy, gdy

  • nieparzysta liczba (większa od 1) zamkniętych par jest połączona (siłą rzeczy liczba komórek węzłów jest parzysta).
  • skrajne komórki węzły (komórki, które należą tylko do jednej zamkniętej pary, czyli pierwsza i ostatnia komórka w pętli) tworzą oddaloną parę o ile te skrajne komórki nie należą do tego samego sektora.
  • jeśli powyżesze dwa warunki są spełnione wówczas możemy usunąć wartości oddalonej pary (kandydatów należących do oddalonej pary) z komórek, które jednocześnie należą do tych samych sektorów co komórki węzły oddalonej pary.

Jak zwykle starałem się opisać to zrozumiale i niespecjalnie wyszło, ale jak to zazwyczaj bywa wszystko stanie się jasne po przedstawieniu Oddalonej pary na przykładach.

Na diagramie obok następujące komórki zawierają po dwóch kandydatów o wartościach "2" i "6":
[1,2], [1,8], [3,3], [3,7], [5,8], [8,1], [8,9], [9,2]
niech symbol → oznacza, że dwie komórki węzły przed i po → tworzą zamkniętą parę, wówczas możemy utworzyć pętlę kolejnych Zablokowanych Par o wartościach "2" i "6":
[8,9]→ [8,1]→ [9,2]→ [1,2]→ [1,8]→ [3,7] Zatem pierwsza pozycja [8,9] oraz ostatnia [3,7] tworzą Odległą Parę o wartościach "2" i "6", więc możemy usunąć powyższe wartości z tych wszystkich pozycji, które leżą na przecięciu sektorów (wiersz/kolumna/blok 3x3) pozycji należących do Oddalonej Pary. W naszym przypadku możemy usunąć wartości "2" i "6" z pozycji: [7,7].

Uwaga : Metoda mająca na celu ustalenie Oddalonej Pary jest nadmiarowa. Mianowicie możesz zamiast niej używać metody Prostego Kolorowania, która nie tylko usunie tych samych kandydatów co metoda Odległych Par, ale często znacznie więcej.

Zastosowanie Prostego Kolorowania dla powyższego przykładu

Na diagramie obok zastosowaliśmy algorytm prostego kolorowania dla wartości "2" otrzymując następujące łańcuchy:
Łańcuch 1: [7,6]→ [5,5]→ [1,8]→ [3,3]→ [4,7]→ [6,1]→ [8,9]→ [9,2]
Łańcuch 2: [7,7]→ [1,8]→ [3,3]→ [4,6]→ [8,1]→ sprzeczność (wartość "2" nie może wystąpić w 2-giej kolumnie)
Wystąpiła sprzeczność w 2-gim łańcuchu , więc z pierwszej pozycji z tego łańcucha usuwamy wartość "2", to jest z pozycji [7,7].

Na tym z kolei diagramie stosujemy metodę prostego kolorowania dla wartości "6" otrzymując następujące łańcuchy:
Łańcuch 1: [8,1]→ [1,2]→ [3,7]→ [5,8]→ [9,9]
Łańcuch 2: [8,9]→ [9,2]→ [1,8]→ [3,3]→ [5,1]
W tym wypadku po zastosowaniu prostego kolorowania kandydatów o wartości "6" możemy usunąc z pozycji: [5,3], [5,9], [6,1], [6,9], [7,7], [9,4], [9,6].

Jak widać zastosowanie metody prostego kolorowania pozwoliło nie tylko na usunięcie tych samych kandydatów z komórki [7,7], niemniej pozwoliło na usunięcie wartości "6" ze znacznie większej liczby komórek niż oddalona para.