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

email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Ryba (Fish)

Termin ryb (ang. fishes) oznacza grupę technik, które pracują w tej samej zasadzie, ale mają ogromną ilość odmian (tak jak prawdziwe ryby) zaczynając od prostych Skrzydlic (ang. X-Wings), a kończąc na rybach FrankenSteina czy też rybach mutantach (jest jeszcze więcej rodzajów ryb dla sudoku i nie wszystkie zostaną opisane (tu zostaną opisane tylko podstawowe ryby). Metody Ryb zajmują się tylko jedną wartością, zatem szukając ryb rozważamy tylko jedną cyfrę. Dla tych technik ważna jest lokalizacja kandydatów w diagramie sudoku.

Zasada podstawowych ryb dla wartości "x" jest następująca: wybieramy "N" podstawowych linii ("N" zależy od rodzaju ryby dla Skrzydlicy N=2 dla Miecznika N=3, a dla Meduzy N=4) [Linia - wiersz lub kolumna], jeśli pozycje zawierające kandydata "x" na tych liniach leżą dokładnie na "N" liniach prostopadłych [kolumn/wierszy] do linii podstawowych to mamy rybę wymiaru "N", wówczas można usunąć kandydata o wartości "x" z komórek, które należą do linii prostopadłych ale nie należą do linii podstawowych. Przykładowo: wybieramy trzy wiersze dla wartości "2", jeśli komórki zawierającego kandydata o wartości "2" na tych trzech wierszach, leżą jednocześnie w dokładnie trzech kolumnach to mamy Miecznik i wówczas możemy usunąć wartość "2" z wszystkich komórek, które należą do tych kolumn, ale nie należą do tych trzech wierszy. Jeśli dalej jest to zawiłe przykłady poniżej wszystko wyjaśnią.

Skrzydlica

Skrzydlica (ang. X-Wing) w rzędach dla wartości "x" występuje wtedy, gdy w dwóch rzędach wszystkie możliwe pola, które kandydują dla wartości "x" leżą w dwóch kolumnach. Analogicznie skrzydlica w kolumnach dla wartości "x" występuje wtedy, gdy w dwóch kolumnach wszystkie możliwe pola, które kandydują dla wartości "x" leżą w dwóch wierszach.

Spójrz na następujący diagram:

Popatrz na pozycje, na których może wystąpić wartość "6" w wierszach "4" i "9".

Kluczem do zrozumienia Skrzydlicy jest wyobrażenie sobie co by się zdarzyło, gdybyś wybrał jedną z tych pozycji i co wtedy stałoby się z innymi pozycjami skrzydlicy.

Wyobraźmy sobie, że lewa górna komórka Skrzydlicy (komórka [4,3]) ma wartość "6" - to wymusiłoby usunięcie drugiego kandydata dla wartości "6" z tego wiersza (pozycja [4,9]) oraz usunięcie dolnego lewego kandydata skrzydlicy (pozycja [9,3]) - wartości na czarnym tle.
To z kolei spowoduje, że w prawa dolna komórca skrzydlicy (pozycja [9,9]) przyjmie wartość "6". Tak więc wstawienie wartości "6" w lewej górnej komórce wymusza, aby w prawej dolnej komórce była też wartość "6"!

Analogicznie, gdyby prawa górna komórka skrzydlicy (pozycja [4,9]) przyjeła wartość "6", to wymusiłoby przyjęcie wartości "6" lewej dolnej komórki skrzydlicy (pozycja [9,3]).

Korzyści wynikające ze stosowania tej metody!

Wniosek jest taki, że jakakolwiek pozycja w górnym rzędzie przyjmie wartość "6" wymusza to przyjęcie wartości "6" w przeciwległej pozycji dolnego rzędu. I to cały sekret - w jednym rzędzie po którejś stronie będzie wartość "6", a w drugim rzędzie po stronie przeciwnej (chociaż nie wiesz, w którym "6" będzie po lewej stronie, a w którym po prawej).

Tak więc w kolumnach "3" i "9" wartość "6" może wystąpić też tylko na dwóch pozycjach (pozycje przecięcia tych kolumn z wierszami skrzydlicy, czyli wierszami "4" i "9"). Tak więc wszystkie inne pozycje tych kolumn nie będą mogły przyjąc wartości "6" (usuwamy z tych pozycji kandydująca wartość "6' - wartości na czarnym tle).
W naszym przypadku pomogło nam to usunąć znacznik "6" z pozycji: [1,3], [1,9], [7,9].

W metodzie tej nowe jest to, że jeśli dostrzeżesz skrzydlicę w wierszach pozwala ci usuwać kandydatów z kolumn. Oczywiście działa to w drugą stronę - dostrzegając skrzydlicę w kolumnach będziesz mogł usuwać kandydatów z wierszy. Dosyć często zdarzy ci się wykryć skrzydlicę, ale nie zawsze pomoże ci to w usunięciu kandydatów.

Porada : Sposobem na dostrzeżenie skrzydlicy jest szukanie prostokątów, którego rogi (komórki rogowe) kandydują do wartości X. Następnie sprawdzasz czy wiersze tego prostokąta bądź kolumny tworzą skrzydlicę. Takie postępując zaoszczędzisz czas!

Kilka przykładów:

Skrzydlica w wierszach dla wartości "8".

Skrzydlica w kolumnach dla wartości "7".

Miecznik

Miecznik (ang. Swordfish) w rzędach dla wartości "x" występuje wtedy, gdy w trzech rzędach wszystkie możliwe pola, które kandydują dla wartości "x" leżą w trzech kolumnach. Analogicznie Miecznik w kolumnach dla wartości "x" występuje wtedy, gdy w trzech kolumnach wszystkie możliwe pola, które kandydują dla wartości "x" leżą w trzech wierszach.

Technika ta jest podobna do Skrzydlicy, ponieważ pozwala ci wykorzystać wiedzę o wierszach do usuwania kandydatów z kolumn i odwrotnie. Zanim przystąpisz do wyszukiwania mieczników upewnij się, że nie masz problemów ze skrzydlicą. Komplikacja w porównaniu ze skrzydlicą polega na tym, że wykorzystujesz wiedzę z 3 wierszy/kolumn w tym samym czasie (znacznie trudniejsze do dostrzeżenia). W Skrzydlicy wystarczyło dostrzec prostokąt!

Ta łamigłówka jest do rozwiązania, ale osiągnęliśmy punkt gdzie prostsze metody nie pomagają.

Tutaj faktycznie występuje Miecznik dla wartości "4", więc wyjaśnimy co to jest i jak to pracuje. Najpierw, wyróżnijmy wszystkie miejsca, gdzie wartość "4" jest kandydatem, to powinno nam ułatwić zadanie.

To co szukamy jest zestawem wartości, który możemy używać do utworzenia łańcucha - podobnie jak przy Skrzydlicy mieliśmy zamknięty łańcuch czterech wartości, Miecznik potrzebuje zamkniętego łańcucha z 6 (albo więcej) wartości.

Miecznik występuje tu w trzech rządach (3, 5 i 8). Usuńmy inne wartości aby diagram był bardziej przejrzysty.

Podobnie jak przy przykładzie na Skrzydlicę, wartość występująca w jednej pozycji wymusza, aby drugi kandydat w tym samym rzędzie nie przyjmował tej wartości.

osyć łatwo na tym przykładzie będzie wytłumaczyć, że wystąpienie wartości "4" w wierszach (3, 5 i 8) determinuje wystąpienie wartości "4" w kolumnach (2, 4 i 7). Można więc powiedzieć, że kolumny (2, 4 i 7) zostały zawłaszczone dla wartości "4".

W naszym przypadku są tylko dwie możliwości wystąpień wartości "4" na pozycjach zaznaczonych powyżej:

1-sza możliwość:
wartość "4" wystąpuje w pozycji [3,2] -> nie może wystąpić w pozycji [8,2] -> musi wystąpić w pozycji [8,7] -> nie może wystąpić w pozycji [5,7] -> musi wystąpić w pozycji [5,4].

2-ga możliwość:
wartość "4" wystąpuje w pozycji [3,4] -> nie może wystąpić w pozycji [5,4] -> musi wystąpić w pozycji [5,7] -> nie może wystąpić w pozycji [8,7] -> musi wystąpić w pozycji [8,2].

Tak czy owak pozycje w wierszach (3, 5 i 8), w których może wystąpić wartość "4" ustalają pozycje w kolumnach (2, 4 i 7), w których może wystąpić wartość "4".

Tak więc możemy usunąć wszystkie kandydujące pozycje z kolumn (2,4,7) dla wartości "4" poza pozycjami należącymi do wierszy Miecznika (3, 5 i 8).

Czasami wykonując taką pracę (znalezienie miecznika) zyskujemy usunięcie tylko jednego kandydata!

Porada : Powyższy przykład był w miarę prosty jak na Miecznik. Należy pamiętać, że miecznik występuje wtedy gdy, pozycje z trzech rzędów/kolumn dla danego kandydata występują tylko w trzech kolumnach/wierszach. Znalezienia miecznika nie zawsze oznacza, że usuniesz jakiegokolwiek kandydata.

Tutaj jest jeszcze jeden przykład: Miecznik w kolumnach dla wartości "1":

Meduza

Meduza (ang. Jellyfish) występuje wtedy, gdy w czterech rzędach wszystkie możliwe pola dla danej wartości leżą w czterech tych samych kolumnach lub odwrotnie, gdy w czterech kolumnach wszystkie możliwe pola dla danej wartości leżą w czterech tych samych rzędach. Meduza występuje bardzo rzadko w zagadkach Sudoku i zazwyczaj będziesz mógł użyć innej techniki do rozwiązania sudoku zamiast się posługiwać techniką Meduzy!

Diagram przedstawia Meduzę dla wartości "4" znalezioną w czterech wierszach 2,4,6,8 z tym, że w każdym wierszu występują cztery pozycje, które mogą przyjąć wartość "4" (jest to Pełna Meduza).

Jak to działa? Wybierzmy dowolną żółtą komórkę diagramu w powyższym przykładzie, który zawiera wartość "4" i załóżmy, że jest to rożwiązanie (wartość "4" jest rozwiązaniem w tej komórce). Niech przykładowo będzie to komórka [2,5], wówczas możemy wyeliminować wartość "4" z wszystkich komórek znajdujących się w 2-gim wierszu i 5-tej kolumnie. Pozostałe komórki kandydujące będą tworzyły Miecznik (komórki: [4,2] [4,7] [4,9] [6,2] [6,7] [6,9] [8,2] [8,7] [8,9]), a jak wiemy w mieczniku wartość "4" może wystąpić tylko na przecięciu wierszy i kolumn należących do miecznika, czyli kandydatami mogą być tylko komórki wyróżnione na żółto, tak więc w Meduzie będzie tak samo, bo niezależnie od wybranej komórki, z komórek wyróżnionych na żółto, rozwiązanie w pozostałych może być też tylko, w innych zółtych komórkach.

Tak więc, w diagramie obok, wartość "4" w kolumnach 2,5,7,9 może wystąpić tylko na żółtych polach, w innych polach z tych kolumn o ile byłyby kandydatem dla wartości "4", należałoby usunąć wartość "4" (komórki na czarnym tle).

Znalezienie Meduzy dla jakiejś wartości, która zawiera dokładnie szesnaście komórek (formacja 4-4-4-4) jest bardzo mało prawdopodobne.

Na diagramie obok jest minimalna Meduza dla wartości "4" w czterech wierszach (formacja 2-2-2-2). Zazwyczaj jednak jeśli wystąpi meduza bedzie to kombinacja dwóch/trzech/czterech pozycji w wierszu/kolumnie.

Na diagramie obok przedstawiono rzeczywisty przykład meduzy. Jest to meduza dla wartości "2" występującą w wierszach 1,4,6,9 (komórki wyróżnione na żółto). Jednocześnie wszystkie te komórki należące do meduzy występują dokładnie w czterech kolumnach: 1,5,8,9. Tak więc możemy usunąc z wszystkich pól kolumn 1,5,8,9 nie należących do meduzy wartość "2". (wartości na czarnym tle)

Jest to formacja meduzy 3-2-3-3.

Tutaj jest następujący przykład Meduzy w wierszach dla wartości "8" stworzony przez Klausa Brennera z Niemiec. Po zastosowaniu techniki meduzy w tym przykładzie otrzymamy niezwykłą liczbę 18 eliminacji wartości "8" (wartości na czarnym tle).