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).
|
|