Wyjątkowy Prostokąt (ang. Avoidable Rectangle) składa się z czterech komórek, które należą
do dwóch wierszy, dwóch kolumn oraz dwóch bloków 3x3. Komórki prostokąta leżące na jednym wierszu nie mają takich samych
wartości jak komórki leżace na drugim wierszu i należące do tego prostokąta. Zadanie sudoku jest wyjątkowe jeśli
wszystkie prostokąty złożone z czterech komórek są wyjątkowe. Praktycznie nigdy nie wiemy czy dane zadanie jest
wyjątkowe, więc metody tutaj omówione nie będą dostępne przy rozwiązywaniu sudoku (chociaż je zaimplementowałem).
Definicja wyjątkowości prostokąta może być niezrozumiała, ale poniższe przykłady wszystko wyjaśnią.
Na tym diagramie prostokąt jest wyjątkowy, gdyż komórki prostokąta leżące w 1-szym wierszu mają
wartości (3,8), a w trzecim (5,8) - czyli nie są takie same. Jeśli przełożemy więc wartości z 1-szego wiersza na 3-ci
i odwrotnie (element [1,1] na [1,3], [3,1] na [1,1], [1,5] na [3,5] oraz [3,5] na [1,5]) wpłynie to na pozostałe elementy
znajdujące się w 1-szym i 3-cim wierszu oraz w 1-szej i 5-tej kolumnie. Na 1-szy i 2-gi blok 3x3 ta zamiana akurat
nie wpłynie.
|
Na tym diagramie w drugim wierszu komórki prostokąta mają wartości (4,5), a w czwartym też (4,5) - ten
prostokąt nie jest wyjątkowy. Możemy więc bezkarnie przełożyć wartości z 2-giego wiersza na wiersz 4-ty
(element [2,2] na [4,2], [4,2] na [2,2], [2,3] na [4,3] oraz [4,3] na [2,3]) i nie wpłynie to na pozostałe wartości tablicy
sudoku. Podobnie będzie jeśli przełożymy wartości z 2-giej kolumny na 3-cią i odwrotnie.
|
Uwaga : techniki tu stosowane są podobne do technik
Unikalnego Prostokąta jednak jest istotna różnica, przy unikalnym prostokącie
eliminujemy martwe układy (zapewniamy, aby dane zadanie sudoku miało tylko jedno rozwiązanie).
Wyjątkowy Prostokąt
Wariant 1. Na tym diagramie mamy trzy komórki wypełnione. Prostokąt będzie
wyjątkowy jeśli w komórce [2,9] nie wystąpi wartość "9" czyli możemy ją usunąć z tej komórki.
|
Wariant 1. To także 1-szy wariant chociaż przypomina trochę martwy
układ, ale nim nie jest. Jeśli komórka [3,4] przyjmie wartość "8" to komórka [3,2]="2", [1,2]="8" oraz [1,4]="2"
i dany prostokąt nie będzie wyjątkowy - sprzeczne, możemy więc usunąć wartość "8" z komórki [3,4].
|
Wariant 2. Załóżmy, że w komórkach [2,1] oraz [3,1] nie wystąpi wartość "2",
wówczas komórka [2,1] przyjmie wartość "1", a [3,1] wartość "7" i mamy sprzeczność (prostokąt nie jest wyjątkowy),
także wartość "2" musi wystąpić w komórce [2,1] bądź [3,1], czyli można usunąć wartość "2" z wszystkich komórek, które
leżą w tym samym sektorze co komórki [2,1] i [3,1] oprócz tych dwóch komórek. W naszym przypadku usuwamy wartość "2"
z komórek: [1,1], [2,2] oraz [8,1].
|
Tu także mamy Wariant 2.
Załóżmy, że w komórkach [3,1] oraz [3,8] nie wystąpi wartość "6", wówczas następujące komórki będą przyjmować wartości
[3,8]="1", [3,1]="5, [2,1]="1" oraz [2,8]="5" (sprzeczność - prostokąt nie jest wyjątkowy), także wartość "6"
musi wystąpić w komórce [3,1] bądź [3,8], czyli można usunąć wartość "6" z wszystkich komórek, które leżą w tym samym
sektorze co komórki [3,1] i [3,8] oprócz tych dwóch komórek. W tym przypadku usuwamy wartość "6" z komórek: [3,2] oraz
[3,3].
|
Wariant 3a. Aby dany prostokąt był wyjątkowy w komórkach [6,2] lub
[6,3] musi wystąpić wartość "1" bądź "3". Te dwie komórki razem z komórką [6,1] tworzą jakby wirtualną
parę o wartościach "1" i "3". Komórki te leżą w 6-tym wierszu oraz w bloku 3x3 o początku w punkcie [4,1] i końcu
w punkcie [6,3], tak więc możemy usunąć wartość "1" i "3" z tych sektorów oprócz komórek [6,1], [6,2] oraz [6,3].
Załóżmy, zę w tym samym sektorze co komórki [6,1], [6,2] i [6,3] inna komórka przyjmie wartość "1" (np. komórka [4,3])
wówczas komórka [6,1] przyjmie wartość "3" tak więc w komórkach [6,2] oraz [6,3] nie będą mogły wystąpić te wartości.
Komórki te przyjmą wartości [6,2]="5" i [6,3]="2" (sprzeczność - prostokąt nie jest wyjątkowy). Zakładając
podobnie, że komórka [4,3] przyjmuje wartość "3" wówczas komórka [6,1] przyjmie wartość "1", więc tak jak w poprzednim
przypadku komórki [6,2] oraz [6,3] nie będą mogły przyjąć wartości "1" oraz "3" a przyjmą wartości "5" oraz "2"
(prostokąt też nie jest wyjątkowy). Wystąpienie wartości "1" bądź "3" w innej komórce niż [6,1], [6,2] oraz [6,3]
leżącej w tym samym sektorze prowadzi do niewyjątkowości układu.
|
Wariant 3b. Podobnie jak na poprzednim diagramie, aby prostokąt był
wyjątkowy w komórce [4,8] badź [6,8] musi wystąpić conajmniej jedna z wartości "4", "6" badź "9". Te dwie komórki
razem z komórkami [1,8] oraz [2,8] tworzą wirtualną trójkę dla wartości "4", "6" i "9". Tak więc, we wszystkich
innych komórkach z 8-smej kolumny możemy usunąć wartości "4", "6" i "9".
|
Wariant 3c. W tym diagramie, aby prostokąt był wyjątkowy w komórkach
[7,3], [9,3] badź [9,9] musi wystąpić conajmniej jedna z wartości "1" badź "2". Te trzy komórki razem z komórką [9,1]
tworzą wirtualną parę dla wartości "1" i "2". Z komórek, które leżą w 9-tym wierszu oraz w bloku 3x3 o początku
w punkcie [7,1] i końcu w punkcie [9,3] (oprócz komórek należących do tego Prostokąta) możemy usunąć wartości "1"
oraz "2". W naszym przypadku usuwamy wartości "1" i "2" z punktu [9,2].
|
Wariant 5a. Wariant ten jest podobny do 2-ego wariantu. Aby prostokąt
był wyjątkowy w komórce [7,8] albo [8,5] musi wystąpić wartość "1". Tak więc możemy usunąć wartość "1" z wszystich
komórek wspólnych z sektorów zawierających komórki [7,8] oraz [8,5] oprócz tych komórek. W naszym przypadku usuwamy
wartość "1" z komórki [7,4].
|
Wariant 5b. W tym przypadku wartość "9" musi wystąpić w jednej z trzech
komórek: [8,6], [8,9] bądź [9,9]. Podobnie jak poprzednio usuwamy wartość "9" 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,6], [8,9] oraz [9,9] to komórki [8,7], [8,8] oraz [8,9]. Komórka [8,9] należy do układu trzech komórek,
komórka [8,8] jest już wypełniona, więc wartość "9" usuwamy z komórki [8,7].
|
Wariant 6. Ten przypadek charakteryzuje się tym, że dwie komórki leżące
po przekątnej prostokąta mają po dwie takie same wartości oraz jedna z tych wartości występuje we wszystkich komórkach
tego prostokąta oraz w wierszach i w kolumnach, na których leżą komórki tego prostokąta wartość ta występuje tylko
w komórkach tego prostokąta. W naszym przypadku wartości "3" i "8" występują w komórkach po przekątnej prostokąta oraz
wartość "3" w wierszach "3" i "6" oraz kolumnach "7" i "9" występuje tylko w komórkach należących do tego prostokąta
(silne wiązania). Tak więc aby prostokąt był wyjątkowy możemy usunąć wartość "3" z tych komórek leżących
na drugiej przekątnej tego prostokąta. W naszym przypadku z komórek [3,9] oraz [6,7].
Załóżmy, że komórka [3,9] przyjmuje wartość "3", wówczas komórki [3,7] i [6,9] przyjmą wartość "8", a komórka [6,7]
wartość "3" (prostokąt nie będzie wyjątkowy). Prostokąt także nie będzie wyjątkowy jeśli komórka [6,7]
przyjmuje wartość "3".
|
Ukryty Wyjątkowy Prostokąt
Wariant 1. Na diagramie znacznie ciężej jest dostrzec kiedy prostokąt
będzie wyjątkowy (dlatego wariant ten nazywamy ukrytym). Komórką bazową jest komórka [3,2], komórka
leżąca na tej samej przekątnej prostokąta co komórka bazowa to [2,9], dla 2-ego wiersza oraz 9-tej kolumny występują
silne wiązania dla wartości "4" oraz wartości te w 2-gim wierszu i 9-tej kolumnie leżą tylko w komórkach tego
prostokąta. Tak więc jeśli komórka [2,9] przyjmie wartość "5" to komórki [2,2] i [3,9] przyjmą wartość "4", a komórka
[3,2] ma już wartość "5" (prostokąt nie będzie wyjątkowy). Należy więc usunąć wartość "5" z komórki [2,9].
|
Tu także mamy Wariant 1. Komórka [3,9] na tej samej przekątnej prostokąta
co komórka [2,6] leży w 3-cim wierszu i 9-tej kolumnie. Wartość "2" w 3-cim wierszu występuje tylko w komórkach
należących do tego zaznaczonego prostokąta, tak samo jest w 9-tej kolumnie (silne wiązania), tak więc jeśli komórka [3,9]
przyjmie wartość "3" to automatycznie komórki [2,9] i [3,6] przyjmą wartość "2", a komórka [2,6] wartość "3" i prostokąt
nie będzie wyjątkowy. Możemy więc usunąć wartość "3" z komórki [3,9].
|
Wariant 2. Dwie komórki mają po dwóch takich samych kandydatów, czyli
tworzą odkrytą parę (w naszym przypadku komórki [2,1] oraz [2,3] o wartościach "6" i "8"). Komórki te leżą w 2-gim
wierszu, więc sprawdzamy czy w kolumnach, w których leżą te komórki występuje silne wiązanie dla jednej z wartości "6"
bądź "8" (w naszym przypadku występuje silne wiązanie w 1-szej kolumnie dla wartości "8" i wartość ta, w 1-szej kolumnie,
leży tylko w komórkach zaznaczonego prostokąta). Można zatem usunąć drugą wartość z komórki, która nie należy do odkrytej
pary oraz nie uczestniczy w silnym wiązaniu dla tej pierwszej wartości (w naszym przypadku usuwamy wartość "6"
z komórki [4,3]).
Załóżmy, że komórka [4,3] przyjmie wartość "6" wówczas komórka [2,3] przyjmie wartość "8", a komórka [2,1] wartość "6",
ponieważ w 1-szej kolumnie wartość "8" występuje tylko w komórkach [2,1] i [4,1], a komórka [2,1] ma już wartość "6", więc
komórka [4,1] przyjmie wartość "8" (prostokąt nie jest wyjątkowy).
|
Rozszerzony Wyjątkowy Prostokąt
Rozszerzony Wyjątkowy Prostokąt (ang. Extended Avoidable Rectangle) składa się z sześciu
komórek, które należą do dwóch wierszy/trzech kolumn/trzech bloków 3x3 albo trzech wierszy/dwóch kolumn/trzech bloków 3x3.
Komórki prostokąta leżące na jednym wierszu/kolumnie) nie mają takich samych wartości jak komórki leżace na drugim
wierszu/kolumnie i należące do tego prostokąta. Zadanie sudoku jest wyjątkowe jeśli wszystkie prostokąty złożone
z sześciu komórek są wyjątkowe. Jest to rozszerzenie wariantu wyjątkowego prostokąta i przypomina warianty
Rozszerzonego Unikalnego Prostokąta.
Wariantów rozszerzonego wyjątkowego prostokąta jest dosyć duzo (wariant 1,2,3a/3b/3c,5a/5b przy części komórek
wypełnionych jak i bez wypełnionych komórek).Warianty te są zaimplementowane jednak nie używane przy rozwiązywaniu sudoku.
Omówię tylko jeden wariant, aby było wiadomo jak to wygląda.
Wariant 2. Na tym diagramie układ sześciu komórek [2,3], [3,3], [2,5], [3,5],
[2,9] oraz [3,9] będzie wyjątkowy jeśli w jednej z komórek [2,5] bądź [2,9] wystąpi wartość "1", można więc usunąć
wartość "1" z wszystkich komórek, które leżą w tym samym sektorze co komórki [2,5] i [2,9] oprócz tych dwóch komórek.
W naszym przypadku wartość "1" usuniemy z komórki [2,8].
Załóżmy, że komórka [2,8] przyjmie wartość "1", wówczas komórka [2,5]=7 a [2,9]=4 (prostokąt nie jest wyjątkowy).
Przełożenie komórek tego prostokąta z 2-ego wiersza na 3-ci i odwrotnie nie wpłynie na pozostałe komórki diagramu sudoku!
|
|