email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Wykluczanie Zestawionych Par (Aligned Pair Exclusion)

Technika Wykluczania Zestawionych Par polega na wyznaczeniu takich dwóch pozycji, które nie mają jeszcze ustalonych wartości, z których jedna wartość z jednej pozycji jest wykluczana z dowolną wartością drugiej pozycji.

  • Zestawione pozycje, jeśli należą do tej samej linii (wiersz/kolumna) muszą być w tym samym bloku 3x3, jeśli zaś nie są w tym samym bloku to wiersze lub kolumny przechodzące przez te Zestawione Pozycje należą do tych samych bloków 3x3 (przykładowo dla sudoku 9x9 wiersz 1-szy i 3-ci należą do tych samych bloków natomiast 1-szy i 4-ty nie).
  • Wykluczanie pary wartości (wartość "x" z jednej Zestawionej Pozycji, wartość "y" z drugiej) polega na:
    • zlalezieniu takiej pozycji. która leży w tym samym sektorze (wiersz/kolumna/blok 3x3) co zestawione pozycje i ma dwie wartości "x" i "y"
    • znalezieniu takich dwóch pozycji, które razem leżą w tym samym sektorze oraz leżą w tym samym sektorze co zestawione pozycje i w sumie mają 3 wartości, przy czym dwie z nich do "x" i "y"
    • znalezieniu takich trzech pozycji, które razem leżą w tym samym sektorze oraz leżą w tym samym sektorze co zestawione pozycje i w sumie mają 4 wartości, przy czym dwie z nich do "x" i "y"
    • jeśli "x" = "y" to wykluczamy taką parę o ile zestawione pozycje leżą w tej samej linii (wiersz/kolumna) oraz w tym samym bloku 3x3
  • Omówienie pokrótce metody Wykluczania Zestawionych Par stanie się bardziej zrozumiałe po zapoznaniu z przykładami przedstawionymi poniżej.

Przykład 1

Na przykładzie obok mamy dwie zestawione pozycje:
[7,2] o wartościach {2,4}
[7,3] o wartościach {2,5,8}
Wszystkie możliwe zestawienia par zakładając, że druga pozycja przyjmie wartość "8" to {2,8} oraz {4,8}. Zakładając, że pozycja [7,2]="2", a pozycja [7,3]="8" to dochodzimy do wniosku, że pozycja [7,9] nie może przyjąć żadnej wartości czyli zestawiona para {2,8} jest wykluczona przez pozycję [7,9], analogicznie para {4,8} jest wykluczona przez pozycję [8,1]. Pozycje [7,9] oraz [8,1] leżą w tym samym sektorze co zestawione pozycje, pozycja [7,9] w tym samym wierszu, a pozycja [8,1] w tym samym bloku 3x3.
Zatem wszystkie możliwe zestawienia wartości "8" z pozycji [7,3] z wszystkimi wartościami pozycji [7,2] zostały wykluczone. Możemy więc usunąć wartość "8" z pozycji [7,3].

Przykład 2

Przykład obok ma dwie zestawione pozycje:
[3,2] o wartościach {1,3,8}
[3,3] o wartościach {3,4,8}
Wszystkie możliwe zestawienia par zakładając, że pierwsza pozycja przyjmie wartość "1" to:
{1,3} para wykluczona przez pozycje [1,1] i [2,3]
{1,4} para wykluczona przez pozycję [3,5]
{1,9} para wykluczona przez pozycję [3,1] i [3,5]
Przeanalizuję tu tylko ostatni wariant. Pozycje [3,1] oraz [3,5] mają w sumie 3 wartości {1,4,9}, jeśli zestawimy parę {1,9} to pozycja [3,1] oraz [3,5] mogą przyjąć tylko wartość "4" (sprzeczne, gdyż dwie wartości "4" wystąpiłyby w 3-cim wierszu).
Zatem wszystkie możliwe zestawienia wartości "1" z pozycji [3,2] z wszystkimi wartościami pozycji [3,3] zostały wykluczone. Możemy więc usunąć wartość "1" z pozycji [3,2].

Przykład 3

Na tym przykładzie, zestawione pozycje to:
[1,8] o wartościach {2,3,5}
[3,4] o wartościach {1,6,7}
Wszystkie możliwe zestawienia par zakładając, że druga pozycja przyjmie wartość "7" to:
{2,7} wykluczona przez pozycje [3,7] i [3,9]
{3,7} wykluczona przez pozycję [3,4], [3,5] i [3,6]
{5,7} wykluczona przez pozycję [3,7] i [3,9]
Przeanalizuję tu tylko 2-gi wariant. Pozycje [3,4], [3,5] oraz [3,6] mają w sumie 4 wartości {2,3,7,8}, jeśli zestawimy parę {3,7} to na tych trzech pozycjach mogą wystąpić tylko dwie wartości "2" i "8", co jest sprzeczne, gdyż jedna z tych wartości musiałaby wystąpić conajmniej 2 razy w 1-szym wierszu.
Zatem wszystkie możliwe zestawienia wartości "7" z pozycji [3,4] z wszystkimi wartościami pozycji [1,8] zostały wykluczone. Możemy więc usunąć wartość "7" z pozycji [3,4].

Przykład 4

Na koniec ciekawy przykład, gdyż prezentuje dosyć dużo wykluczeń. Zestawione Pozycje to:
[4,5] o wartościach {1,2,6,7,9}
[5,5] o wartościach {2,4,7,9}
Wszystkie możliwe zestawienia par zakładając, że druga pozycja przyjmie wartość "2" to:
{1,2} wykluczona przez pozycję [2,5]
{2,2} wykluczona bo dwe wartości "2" występują w tym samym bloku 3x3
{6,2} wykluczona przez pozycję [4,6]
{7,2} wykluczona przez pozycję [5,6]
{9,2} wykluczona przez pozycję [3,5]
Zatem wszystkie możliwe zestawienia wartości "2" z pozycji [5,5] z wszystkimi wartościami pozycji [4,5] zostały wykluczone. Możemy więc usunąć wartość "2" z pozycji [5,5].