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

email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Rozszerzony Unikalny Prostokąt (Extended Unique Rectangle)

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.