email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Wyjątkowy Prostokąt (Avoidable Rectangle)

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!