Wdrożyłem kolejną metodę 'Fireworks'.
Teraz pracuję nad metodą 'Pętle SK'.

email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Unikalny Prostokąt (Unique Rectangle)

Metoda Unikalnego Prostokąta (ang. Unique Rectangle) 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. Metoda ta jest bardzo przydatna i ma kilka interesujących wariantów, które przedstawię poniżej, niemniej jednak trzeba omówić martwy układ - co to jest i z czym to się je.

Na diagramie obok cztery komórki tworzą prostokąt z czterech sprzężonych par o wartościach "4" i "5". Komórki te leżą w dwóch rzedach, w dwóch kolumnach oraz w dwóch blokach 3x3. Mając taką grupę czterech par nie jest możliwe otrzymanie jednego rozwiązania.

Możliwe rozwiązanie to [2,2]=4, [2,3]=5, [4,2]=5 oraz [4,3]=4, ale możliwe jest także rozwiązanie [2,2]=5, [2,3]=4, [4,2]=4 oraz [4,3]=5. W obydwu przypadkach wartości "4" i "5" zostaną wstawione w te same dwa rzędy, kolumny oraz bloki 3x3, więc możliwe są dwa rozwiązania (te cztery komórki tworzą martwy układ (ang. deadly pattern). Jeśli osiągnąłeś taki stan w rozwiązaniu to coś poszło nie tak! Algorytm Unikalnego Prostokąta polega właśnie na unikaniu martwych układów.

Na tym diagramie cztery komórki z wartościami "7" i "9" wyglądają jakby tworzyły martwy układ, ale jest zasadnicza różnica. Komórki nadal znajdują się w dwóch rzędach i dwóch kolumnach jednak należą do czterech różnych bloków. Więc w zależności od rozwiązania w każym z tych czterech bloków będą wstawione różne wartości, więc i rozwiązania będą różne. Taki układ choć przypomina nie tworzy martwego układu!

Unikalny Prostokąt

Podstawowym warunkiem wykorzystania tej metody jest znalezienie pierwszej komórki, która ma dwie wartości. A następnie trzy kolejne, które z poprzednią komórką tworzą prostokąt oraz mają wszystkie te dwie wartości co pierwsza komórka. Oczywiście, te trzy komórki mogą zawierać także inne wartości niż ma 1-sza komórka, ale warunkiem koniecznym jest, aby miały te dwie wartości co pierwsza komórka (bez tego warunku nie ma zagrożenia martwym układem).

Wariant 1. Na diagramie obok trzy komórki zawierają wartości "8" i "9". Aby nie dopuścić do martwego układu w komórce [2,2] nie może być ani wartości "8" ani "9". Czyli możemy usunąć wartość "8" i "9" z komórki [2,2].

Załóżmy, że żadna komórka, która leży w sektorze komórki [2,2] (2-gi wiersz, 2-ga kolumna, 1-szy blok 3x3) nie zawiera wartości "8" oraz "9" oprócz komórek należących do prostokąta. Gdyby w 2-gim wierszu nie byłoby wartości "8" i "9" opróćz komórek należących do prostokąta, to komórki [2,2] i [2,3] tworzyłyby ukrytą parę o wartościach "8" i "9", więc musielibyśmy usunąć wartość "3" z komórki [2,2] (powstałby martwy układ). Czyli, przynajniej jedna z komórek nie należących do prostokąta musi zawierać wartość "8" bądź "9" (to przynajmniej jedna z komórek [2,3] lub [6,2] będzie zawierać wartość przeciwną "9" bądź "8") - tak więc wychodzi na to samo, że komórka [2,2] nie może zawierać wartości "8" oraz "9".

Wariant 2a. Na tym diagramie układ czterech komórek [6,5], [6,6], [8,5] i [8,6] nie utworzy martwego układu jeśli w jednej z komórek [8,5] bądź [8,6] wystąpi wartość "7". W tym przypadku można usunąć wartość "7" z wszystkich komórek, które leżą w tym samym sektorze co komórki [8,5] i [8,6] oprócz tych dwóch komórek. W naszym przypadku wartość "7" usuniemy z komórek: [7,4], [7,5], [7,6], [8,3], [8,8], [9,4], [9,5] oraz [9,6].

Załóżmy, że jakakolwiek z komórek, z której usuneliśmy wartość "7" przyjmuje wartość "7", wówczas z komórki [8,5] oraz [8,6] usuwamy wartość "7" i mamy martwy układ utworzony przez komórki zaznaczone na żółto.

Wariant 2b. Wariant ten jest podobny do 2a wariantu. Aby uniknąć martwego układu 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].

Załóżmy, że komórka [7,4] przyjmie wartość "1" wówczas należy usunąć wartość "1" z komórek [7,8] oraz [8,5] i oczywiście powstanie martwy układ, czyli w komórce [7,4] nie może być wartości "1".

Wariant 2c. W tym przypadku wartość "6" musi wystąpić w jednej z trzech komórek: [8,6], [8,9] bądź [9,9]. 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,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ść "6" usuwamy z komórki [8,7].

Niech komórka [8,7] przyjmie wartość "6", wówczas z komórek [8,6], [8,9] oraz [9,9] musimy usunąć wartość "6" i wystąpi martwy układ, czyli komórka [8,7] nie może zawierać wartości "6".

Wariant 3a. Aby uniknąć matwego układu na diagramie obok 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. Mamy martwy układ. 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". Mamy także martwy układ w komórkach [6,2], [6,3], [8,2] oraz [8,3]. 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 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,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] tworzy 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 "3b" można udowodnić postępując analogicznie jak w wariancie poprzednim "3a".

W tym diagramie, aby uniknąć martwego układu 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] tworza 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 Unikalnego Prostokąta oraz komórki [9,1]) możemy usunąć wartości "1" oraz "2". W naszym przypadku usuwamy wartości "1" i "2" z punktu [9,2].

Załóżmy, że komórka [9,2] przyjmie wartość "1" to komórka [9,1] przyjmie wartość "2", więc z komórek [7,3], [9,3] oraz [9,9] usuwamy wartości "1" i "2" - powstanie martwy układ.

Wariant 4. W tym przypadku należy zauważyć, że w 8-smym wierszu wartość "7" występuje tylko w komórkach [8,1] i [8,2]. Jeśli więc jeśli jedna z tych komórek przyjmie wartość "9" to automatycznie druga z nich przyjmie wartość "7" co razem z komórkami [1,1] i [1,2] doprowadzi do martwego układu. Tak więc należy usunąć wartość "9" z komórek [8,1] i [8,2].

Załóżmy, że żadna komórka leżąca w tym samym sektorze co komórki [8,1] i [8,2] (8-smy wiersz, 7-my blok 3x3) nie zawiera wartości "9" oprócz komórek [8,1] oraz [8,2], wówczas komórki [8,1] i [8,2] utworzyłyby ukrytą parę o wartościach "7" i "9", więc usunelibyśmy z tych komórek wszystkie wartości oprócz "7" i "9" - powstałby martwy układ. Udowadniając sprzeczność załóżenia udowodniliśmy prawdziwość przeciwnego założenia, że przynajmniej jedna komórka leżąca w tym samym sektorze co komórki [8,1] i [8,2] ma wartość "9" oprócz tych komórek [8,1] oraz [8,2] czyli, że z komórek [8,1] oraz [8,2] należy usunąć wartość "9", aby nie dopuścić do martwego układu.

Wariant 5. Ten przypadek charakteryzuje się tym, że dwie komórki leżące po przekątnej prostokąta, w którym może wystąpić martwy układ, 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 "2" i "5" występują w komórkach po przekątnej prostokąta oraz wartość "5" w wierszach "4" i "5" oraz kolumnach "3" i "4" występuje tylko w komórkach należących do tego prostokąta (silne wiązania). Tak więc możemy usunąć wartość "5" z tych komórek leżących na drugiej przekątnej tego prostokąta. W naszym przypadku z komórek [4,3] i [5,4].

Załóżmy, że komórka [4,3] przyjmuje wartość "5", wówczas komórki [4,4] i [5,3] przyjmą wartość "2", a komórka [5,4] wartość "5" (wystąpi martwy układ). Do martwego układu dojdziemy również zakładając, że komórka [5,4] przyjmuje wartość "5".

Ukryty Unikalny Prostokąt

Wariant 1. Na diagramie cztery zaznaczone komórki zawierają wartości "1" i "6", więc teoretycznie może wystąpić martwy układ, ale zastosowanie dotychczas znanych wariantów nic nie da (nie łatwo go dostrzec dlatego nazywamy go ukrytym). Komórka [4,3] na tej samej przekątnej prostokąta co komórka [6,7] leży w 4-tym wierszu i 3-ciej kolumnie. Wartość "1" w 4-tym wierszu występuje tylko w komórkach należących do tego zaznaczonego prostokąta, tak samo jest w 3-ciej kolumnie (silne wiązania), tak więc jeśli komórka [4,3] przyjmie wartość "6" automatycznie komórki [4,7] i [6,3] przyjmą wartość "1", a komórka [6,7] wartość "6" (wystąpi martwy układ). Nie dopuszczamy do martwego układu usuwając wartość "6" z komórki [4,3].

Wariant 2. Tu występuje jeszcze inny wariant nie ujęty w poprzednich wariantach. 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" (mamy martwy układ).