email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

3D Medusa (Trójwymiarowa Meduza)

Trójwymiarowa Meduza (ang. 3D Medusa) opiera się na bi-lokalizacji - wartość "x" ma dwie kandydujące pozycje dla tej wartości w danym sektorze (wiersz/kolumna/blok 3x3) oraz na bi-wartości - komórki o dwóch kandydujących wartościach. W odróżnieniu od prostego kolorowania, które odbywało się dla jednej wartości w 3D Meduza wprowadzono trzeci wymiar - coś jakby kolorowanie dla wielu wartości.

Algorytm zaczynamy od wyznaczenia jakiejś komórki startowej, która ma dwie wartości, następnie dla pierwszej wartości z tej komórki tworzymy sieć wszystkich możliwych połączeń oznaczonych kolorem czerwonym, a dla drugiej wartości z komórki startowej tworzymy także sieć wszystich możliwych połączeń oznaczonych kolorem niebieskim. Połączenia w tak utworzonej sieci połączeń mogą być lokacyjne lub wartościowe.
Połączenie lokacyjne - niech komórki A i B są bi-lokacyjne dla wartości "x" w jakimś sektorze oraz komórki B i C są bi-lokacyjne dla wartości "x" w jakimś innym sektorze, wówczas jeśli komórka A przyjmie wartość "x" to komórka B nie będzie mogła przyjąć wartości "x", a to spowoduje przyjęcie przez komórkę C wartości "x", analogicznie jeśli komórka C przyjmie wartość "x" wówczas komórka A przyjmie też wartość "x". Jeśli z kolei komórka A nie przyjmie wartość "x" to również komórka C nie przyjmie tej wartości, więc jeśli będziemy usuwać kandydata "x" z komórki A możemy go usunąć również z komórki C.
połączenie wartościowe - niech komórki A i B są bi-lokacyjne dla wartości "x w jakimś sektorze oraz komórka B ma dwie wartości "x" i "y", wówczas jeśli komórka A przyjmie wartość "x" to komórka B nie przyjmie tej wartości, a więc przyjmie wartość "y", odwrotnie jeśli komórka B przyjmie wartość "y" to komórka A przyjmie wartość "x". Jeśli z kolei komórka A nie przyjmie wartości "x" to komórka B nie przyjmie wartości "y" i odwrotnie jeśli komórka B nie przyjmie wartości "y" to komórka A nie przyjmie wartości "x". Analogicznie jak przy połączeniu lokacyjnym jeśli usuniemy wartość "x" z komórki A to możemy również usunąć wartość "y" z komórki B.

Po utworzeniu dwóch sieci połączeń z komórki startowej oznaczonych dwoma różnymi kolorami istnieje 7 wariantów na podstawie których będziemy wyznaczać kandydatów do usunięcia. Warianty te są omówione poniżej.

Wariant 1: podwójnie w komórce

W tym wariancie tworząc sieć połączeń dochodzimy do sytuacji, że w pewnej komórce dwie wartości są tego samego koloru. Jest to sprzeczne, bo komórka może przyjąć tylko jedną wartość!

Na diagramie obok mamy przykład Meduzy 3D w pierwszym wariancie. Załóżmy, że komórka startowa to [2,5]. Zaczynamy więc budować łańcuch połączeń dla wartości "3" z komórki startowej oznaczony kolorem czerwonym oraz dla wartości "9" oznaczony kolorem czarnym. Niech [x1,y1]=a->[x2,y2]=b oznacza, że jeśli komórka [x1,y1] przyjmie wartość "a" to komórka [x2,y2] przyjmie wartość "b" otrzymamy zatem następujące sieci połączeń:
kolor czerwony: [2,5]=3->[2,7]=9->[3,7]=4, [2,7]=9->[2,1]=4->[3,2]=1->[8,1]=1, [2,5]=3->[9,5]=9->[8,4]=3->[9,2]=3, [2,5]=3->[3,4]=9
kolor czarny: [2,5]=9->[2,7]=4->[3,7]=9, [2,7]=4->[3,2]=4->[8,2]=1, [2,5]=9->[9,5]=3->[8,2]=3
jak widać na diagramie założenie, że komórka [2,5] przyjmie wartość "9" doprowadza do tego, że komórka [8,2] musi przyjąć jednocześnie dwie wartości "1" i "3" co jest niemożliwe, zatem możemy usunąć wartość "9" z komórki startowej, ale ponieważ wszystkie polączenia są lokacyjne bądź wartościowe, więc możemy usunąć całą sieć połączeń dla wartości "9" w komórce startowej (wszystkie wartości oznaczone kolorem czarnym).

Wariant 2: podwójnie w sektorze

Wariant ten ma miejsce, gdy tworząc sieć połączeń dla pewnej wartości komórki startowej dochodzimy do tego, że w pewnym sektorze (wiersz/kolumna/blok 3x3) wartość "x" jest oznaczona tym kolorem dwukrotnie. Jest to sprzeczne, gdyż doprowadzi do tego, że wartość "x" wystąpi dwukrotnie w tym sektorze. W tym przypadku podobnie jak w 1-szym wariancie usuwamy całą sieć połączeń, która prowadzi do sprzeczności.

Na diagramie obok mamy utworzone dwie sieci połączeń począwszy od punktu startowego [1,7] oznaczone dla wartości "4" kolorem czerwonym i dla wartości "6" kolorem czarnym. Jak widać wartość "7" występuje dwukrotnie w 7-dmej kolumnie na pozycjach [2,7] oraz [9,7] w tym samym kolorze czarnym, zatem możemy usunąć wszystkie wartości oznaczone kolorem czarnym.

.

Wariant 3: dwa kolory w komórce

Pewna komórka ma dwie wartości "x" i "y" w różnych kolorach, czyli niezależnie od tego jaką wartość przyjmie komórka startowa ta pewna komórka może przyjąć tylko wartości "x" bądź "y" (pokolorowane), czyli możemy usunąć z tej komórki wszystkie inne wartości (niepokolorowane).

Na diagramie obok komórka [3,2] ma dwie wartości w różnych kolorach: wartość "3" w czerwonym oraz "7" w niebiekim. Możemy więc usunąć z tej komórki wszystkie inne wartości: w naszym przypadku usuwamy wartość "8".

Wariant 4: dwa kolory w sektorze

Dwie komórki A i B leżą w tym samym sektorze oraz komórka A ma wartość "x" oznaczoną jednym kolorem, a komórka B ma wartość "x" oznaczoną drugim kolorem. Oznacza to, że niezależnie od tego jaką wartość przyjmie komórka startowa wartość "x" w pewnym sektorze może wystąpić tylko w punktach A lub B, czyli możemy usunąć wartość "x" z wszystkich innych komórek tego sektora.

W naszym przykładzie obok wartość "5" jest oznaczona kolorem niebieskim w punkcie [4,7] oraz kolorem czerwonym w punkcie [6,7]. Obydwa punkty leżą w 7-mej kolumnie oraz bloku 3x3 o początku w pukcie [4,7] i końcu w punkcie [6,9], tak więc można usunąć z wszystkich innych komórek tych sektorów wartość "5", czyli z komórek [1,7], [3,7], [7,7], [4,8], [5,8], [5,9]. Oznaczone na czarno wartości "5" (czyli do usunięcia) z komórek [6,2] i [7,4] prezentują inne warianty: w komórce [6,2] wariant 6, a w komórce [7,4] wariant 5. Opis tych wariantów znajdziesz poniżej.

Wariant 5: dwa kolory 'gdziekolwiek'

Dwie komórki A i B leżą w różnych sektorach oraz komórka A ma wartość "x" oznaczoną jednym kolorem, a komórka B ma wartość "x" oznaczoną drugim kolorem. W tym przypadku możemy usunąć wartość "x" z pozycji, które leżą na przecięciu sektorów zawierających komórki A i B.

W naszym przykładzie obok wartość "6" jest oznaczona kolorem niebieskim w punkcie [6,5] oraz kolorem czerwonym w punkcie [5,9]. Pozycje [6,8] oraz [6,9] leżą w tym samym wierszu co komórka [6,5] oraz w tym samym bloku co komórka [5,9], tak więc możemy usunąć z tych komórek wartość "6".

Wariant 6: dwa kolory komórka+sektor

Komórka A ma wartość "x" oznaczoną jednym kolorem oraz komórka B leżąca w tym samym sektorze co komórka A ma wartość "y" oznaczoną innym kolorem. Oznacza to, że niezależnie od wybranej wartości w komórce startowej, komórka A może przyjąć wartość "x" (czyli nie może przyjąć wartości "y") albo komórka B przyjmie wartość "y" (komórka A nie może przyjąć wartości "y" bo komórka B leży w tym samym sektorze co komórka A), możemy usunąć wartość "y" z komórki A.

W naszym przykładzie obok komórka [3,5] ma wartość "9" oznaczoną kolorem czerwonym oraz komórka [3,9] leżąca w tym samym wierszu co komórka [3,5] ma wartość "8" oznaczoną kolorem niebieskim, tak więc możemy usunąć wartość "8" z komórki [3,5]. Ten sam wariant jest zastosowany w komórkach [3,7], [5,4] i [5,5].

Wariant 7: komórka opróżniona przez kolor

Załóżmy, że zapis kandydat "x" z komórki A widzi pewien kolor, jeśli istnieje komórka B leżąca w tym samym sektorze co komórka A, która ma oznaczoną wartość "x" tym pewnym kolorem.

Zatem wariant ten występuje wtedy, gdy istnieje taka komórka, która nie ma żadnego pokolorowanego kandydata oraz każdy kandydat z tej komórki widzi ten sam kolor! Jeśli ten kolor stanowiłby rozwiązanie to wówczas z tej komórki zostałyby usunięte wszystkie wartości, tak więc nie można by wstawić w tą komórkę żadnej wartości co jest oczywiście sprzeczne. Można więc usunąć całą sięć połączeń oznaczoną tym kolorem, który powoduje tą sprzeczność.

W naszym przykładzie obok komórka [3,6] ma kandydatów "4", "6" i "9" i wszyscy są widoczni przez ten sam kolor ("4" w komórce [1,6], "6" w komórce [9,6] oraz "9" w komórce [3,7]), tak więc można usunąć wszystkich kandydatów oznaczonych tym kolorem (kolor czarny).