Metoda Rozszerzonego Unikalnego Prostokąta (ang. Extended Unique Rectangle) podobnie jak medota
Unikalnego Prostokąta korzysta z faktu, że publikowane zadania sudoku mają tylko jedno rozwiązanie
(zazwyczaj tak jest). Jeśli nie ma takiej gwarancji ta technika nie zadziała. Niemniej jednak zanim omówię kolejne warianty
tej techniki muszę najpierw rozszerzyć pojęcie martwego układu.
Martwy układ komórek mamy wtedy, gdy żadne wartości spoza tych komórek nie mogą wpłynąć na komórki tego układu (wówczas
komórki te tworzą nienaruszalny układ - niemożliwe jest wyeliminowanie jakiegokolwiek kandydata z tych komórek).
Wiemy już kiedy cztery komórki tworzą martwy układ (Unikalny Prostokąt). Rozszerzony martwy
układ występuje wtedy gdy 9-wieć komórek, leży w trzech wierszach, trzech kolumnach i trzech blokach 3x3 i ma w sumie trzech
kandydatów, czyli w każdym z tych sektorów wystąpi odkryta trójka. My jednak uprościmy tą wersję
do 6-ciu komórek występujących w 2-wierszach, 3-kolumnach, 3-blokach 3x3 bądź 3-wierszach, 2-kolumnach, 3-blokach 3x3 o trzech
kandydatach.
Na rysunku sześć komórek [1,1], [3,1], [1,5], [3,5], [1,9] oraz [3,9] tworzą rozszerzony prostokąt o
wartościach "1", "2" i "3" (dwa wiersze, trzy kolumny, trzy bloki 3x3), te komórki tworzą martwy układ, gdyż żadna
wartość spoza tych komórek nie może wyeliminować jakiegokolwiek kandydata z tego układu komórek.
Komórki tego rozszerzonego prostokąta w wierszach tworzą odkryte trójki, natomiast w kolumnach i blokach 3x3 odkryte
pary, czyli komórki te są nienaruszalne (nie można z nich wyeliminować żadnago kandydata), więc utworzą więcej niż jedno
rozwiązanie.
|
Na tym przykładzie nie jest już tak słodko, bo owszem w kolumniach 1-szej i 3-ciej są odkryte trójki
ale w wierszach i blokach nie ma odkrytych par, a więc inne komórki z bloków i wierszy, gdzie znajdują się komórki
rozszerzonego prostokąta (oprócz komórek, które znajdują się w kolumach "1" i "3") - nazwijmy je komórkami przyprostokątnymi
- mogą wpływać na komórki prostokąta, ale na dwie komórki naraz!!! (przykładowo komórka [2,3] przyjmie wartość "2" to wówczas
wpłynie to na dwie komórki rozszerzonego prostokąta [1,1] oraz [1,3] (zostanie z nich usunięta wartość "2"). W naszym przypadku
to komórki należące do wiersza "1", "5" oraz "9" oraz do 2-giej kolumny oprócz komórek należących do rozszerzonego prostokąta to
komórki przyprostokątne. Wiersze badź kolumny zbudowane z komórek przyprostokątnych nazwiemy wierszami/kolumnami
przyprostokątnymi.
Załóżmy, że w trzech wierszach przyprostokątnych wystąpią wartości od "1" do "3" (przykładowo w 1-szym wierszu wartość
"2" w 5-tym "3" w 9-tym wartość "1") wówczas komórki rozszerzonego prostokąta bedą miały wartości: [1,1]=(1,3), [1,3]=(1,3),
[5,1]=(1,2), [5,3]=(1,2), [9,1]=(2,3) i [9,3]=(2,3) powstanie martwy układ (zobacz powyższy diagram). Teraz załóżymy, że
jakaś z wartości "1", "2" lub "3" wystąpi w dwóch wierszach przyprostokątnych, przykładowo wartość "2" wystąpi w wierszu
1-szym i 9-tym. wówczas komórki: [1,1]=(1,3), [1,3]=(1,3), [9,1]=(1,3) oraz [9,3]=(1,3) utworzą martwy układ dla prostokąta
zbudowanego z czterech komórek.
Można udowodnić, że każdy układ 6-ciu komórek mających w sumie trzy wartości zbudowanych w ten sposób, że każde dwie komórki
z trzech wierszy lub trzech kolumn mających po dwie lub trzy takie same wartości tworzą martwy układ.
|
Na tym diagramie, komórki 1-szej kolumny bedą wpływać na wartości komórek [1,1] oraz [2,1], więc nie może
być mowy o rozszerzonym martwym układzie. Martwy układ mogłby wystąpić tylko, gdyby ta sama wartość od "1" do "3" wystąpiła
w kolumnach 5-tej i 9-tej wówczas komórki [1,5], [2,5], [1,9] oraz [2,9] utworzyłyby martwy układ dla czterech komórek
(wariant dla Unikalnego Prostokąta) - tutaj jednak interesuje nas tylko rozszerzony martwy układ.
|
Wariant 1. Na diagramie obok pięć komórek zawiera wartości "1", "3" i "5".
Aby nie dopuścić do martwego układu w komórce [3,1] nie może być wartości "1", "3" oraz "5". Czyli możemy usunąć
wartość "1" i "5" z komórki [3,1].
Załóżmy, że żadna komórka, która leży w sektorze komórki [3,1] (3-ci wiersz, 1-sza kolumna, 1-szy blok 3x3) nie zawiera
wartości "1", "3" oraz "5" oprócz komórek należących do tego rozszerzonego prostokąta. Gdyby w 3-cim wierszu nie byłoby
wartości "1" i "5" opróćz komórek należących do prostokąta, to komórki [3,1] i [3,3] tworzyłyby
ukrytą parę o wartościach "1" i "5", więc musielibyśmy usunąć wartość "1" z komórki [3,1]
(powstałby martwy układ). Czyli, przynajniej jedna z komórek leżących w tym samym sektorze, co komórka [3,1], nie
należących do prostokąta musi zawierać wartość "1" bądź "5" (w konsekwencji komórka [3,3] bądź komórki [5,1] oraz [7,1]
usuną drugą wartość z komórki [3,1]). Przykładowo niech [3,5]=1 to [3,3]=5, więc [3,1] różne od 1 i 5, analogicznie niech
[4,1]=5 to [5,1]=(1,3),[7,1]=(1,3) - odkryta para, więc [3,1] różne od "1" i "5", tak więc wychodzi na to samo, że komórka
[3,1] nie może zawierać wartości "1" oraz "5".
|
Wariant 2a. Na tym diagramie układ sześciu komórek [3,1], [3,3], [5,1], [5,3],
[7,1] oraz [7,3] nie utworzy martwego układu jeśli w jednej z komórek [3,1] bądź [5,1] wystąpi wartość "6". W tym przypadku
można usunąć wartość "6" z wszystkich komórek, które leżą w tym samym sektorze co komórki [3,1] i [5,1] oprócz tych dwóch
komórek. W naszym przypadku wartość "6" usuniemy z komórki [6,1].
Załóżmy, że jakakolwiek z komórek, z której usuneliśmy wartość "6" przyjmuje wartość "6", wówczas z komórek [3,1] oraz [5,1]
usuwamy wartość "6" i mamy rozszerzony martwy układ utworzony przez komórki zaznaczone na żółto.
|
Wariant 2b. Wariant ten jest podobny do 2-ego wariantu.
Aby uniknąć martwego układu w komórce [1,6] albo [5,5] musi wystąpić wartość "2". Tak więc możemy usunąć
wartość "2" z wszystich komórek wspólnych z sektorów zawierających komórki [1,6] oraz [5,5] oprócz tych komórek.
W naszym przypadku usuwamy wartość "2" z komórek [2,5], [3,5] oraz [6,6].
Załóżmy, że komórka [3,5] przyjmie wartość "2" wówczas należy usunąć wartość "2" z komórek [1,6] oraz [5,5]
i oczywiście powstanie martwy układ, czyli w komórce [3,5] nie może być wartości "2".
|
Wariant 2c. W tym przypadku wartość "6" musi wystąpić w jednej z trzech
komórek: [8,5], [9,1] bądź [9,5]. Podobnie jak poprzednio usuwamy wartość "6" z wszystkich wspolnych komórek sektorów
zawierających te trzy komórki opróch tych trzech komórek. W naszym przypadku komórki należące do tego samego sektora
co komórki [8,5], [9,1] oraz [9,5] to komórki [9,4], [9,5] oraz [9,6]. Komórka [9,5] należy do układu trzech komórek,
więc wartość "6" usuwamy z komórek [9,4] oraz [9,6].
Załóżmy, że komórka [9,6] przyjmie wartość "6" wówczas należy usunąć wartość "6" z komórek [9,1], [9,5] oraz [8,5],
więc powstanie martwy układ co jest równoznaczne z tym, że w komórce [9,6] nie może być wartości "6".
|
Wariant 3a. Aby uniknąć matwego układu na diagramie obok w komórkach
[2,1] lub [6,1] musi wystąpić wartość "3" bądź "8". Te dwie komórki razem z komórką [4,1] tworzą jakby wirtualną
parę o wartościach "3" i "8". Komórki te leżą w 1-szej kolumnie, tak więc możemy usunąć wartość "3" i "8" z 1-szej kolumny
oprócz komórek [2,1], [6,1], [8,1] oraz [4,1].
Załóżmy, zę w tym samym sektorze co komórki [2,1], [4,1], [6,1] i [8,1] inna komórka przyjmie wartość "8" (np. komórka [3,1])
wówczas komórka [4,1] przyjmie wartość "3" tak więc w komórkach [2,1], [6,1] oraz [8,1] nie będą mogły wystąpić te wartości. Mamy
martwy układ. Wystąpienie wartości "3" bądź "8" w innej komórce niż [2,1], [4,1], [6,1] oraz [8,1] leżącej w 1-szej
kolumnie prowadzi do martwego układu, czyli dopuszcza do więcej niż jednego rozwiązania, co jest sprzeczne z naszym
założeniem!
|
Wariant 3b. Podobnie jak na poprzednim diagramie, aby uniknąć
martwego układu w komórce [4,6] badź [5,6] musi wystąpić conajmniej jedna z wartości "1", "5" badź "6".
Te dwie komórki razem z komórkami [2,6] oraz [9,6] tworzą wirtualną trójkę dla wartości "1", "5" i "6".
Tak więc, we wszystkich innych komórkach z 6-tej kolumny możemy usunąć wartości "1", "5" i "6".
Wariant "3b" można udowodnić postępując analogicznie jak w wariancie poprzednim "3a".
|
Wariant 3c. W tym diagramie, aby uniknąć martwego układu w komórkach
[1,5], [1,8] badź [2,5] musi wystąpić conajmniej jedna z wartości "2" badź "7". Te trzy komórki razem z komórką [1,4]
tworzą wirtualną parę dla wartości "2" i "7". Z komórek, które leżą w 1-szym wierszu oraz w bloku 3x3 o początku
w punkcie [4,1] i końcu w punkcie [6,3] (oprócz komórek należących do Unikalnego Prostokąta oraz komórki [1,4]) możemy usunąć
wartości "2" oraz "7". W naszym przypadku usuwamy wartości "2" z punktu [1,6].
Załóżmy, że komórka [1,6] przyjmie wartość "2" to komórka [4,1] przyjmie wartość "7", więc z komórek [1,5], [1,8] oraz
[2,5] usuwamy wartości "2" i "7" - powstanie martwy układ.
|
|