email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Forsowanie Błędu (Nishio)

Technika "Forsowania Błędu" (dalej będziemy zwać ją "Nishio") polega na wyborze jakiejś komórki startowej z dwoma kandydatami i przyjęciu jednej z tych dwóch wartości dla tej komórki. Następnie kontunuujesz rozwiązywanie sudoku od tego punktu (podobnie jak przy "Forsownych Łańcuchach"). Jeżeli rozwiązując sudoku od tego punktu dojdziesz do końca i wynik okaże się poprawny to wspaniale - zgadłeś! Jeśli twój wybór był zły to dojdziesz do sprzeczności (sprzeczność występuje wtedy, gdy pewna wartość [od 1 do 9] wystąpi dwa razy w tym samym wierszu / kolumnie/ kwadracie 3x3 bądź w jakiejś komórce nie będzie żadnych możliwych kandydatów do wyboru). Do sprzeczności możesz dojść raptem po paru kolejno wyznaczonych komórkach bądź dopiero przy końcu rozwiązywania sudoku.

Znalezienie sprzeczności oznacza, że kandydat wybrany w komórce startowej może być usunięty, zatem drugi kandydat z tej komórki będzie poprawny. Jeżeli pechowo wybrałeś poprawną wartość dla jakiejś komórki startowej (nie wiesz tego!) nie jest to korzystne, ponieważ nie możesz być pewien czy wybór twój jest dobry czy zły, dopóki nie rozwiążesz całego sudoku. Niektórzy po ustaleniu kandydata w komórce startowej wyznaczają kilka kolejnych komórek i jeśli nie dojdą do sprzeczności to wybierają innego kandydata w tej samej komórki lub innej by zyskać na czasie.

Zobacz na diagram z wyróżnioną komórką:

Ustalmy, że komórka startowa [1,2] ma wartość "8" i kontynuujmy rozwiązywanie forsując wartości w kolejnych komórkach.

Bez zbytniego wysiłku wykreślimy wykluczonych kandydatów (kandydaci przekreśleni na czerwono) i wyróżnimy na niebiesko pojedyńczych kandydatów, którzy staną się nowymi zawartościami komórek.

Można by dalej forsować kolejne komórki (te, w których nie ma pojedyńczego kandydata wyróżnionego na niebiesko), ale dla naszego przykładu te wyznaczone są wystarczające.

Po ustaleniu wartości w komórce startowej wyznaczyliśmy wielu pojedyńczych kandydatów (wartości wyróżnione na niebiesko), ale spójrz na komórkę [8,9], która ma dwóch kandydatów "2" i "3".

W kolumnie "9" mamy wartości "2" (w komórce [5,9]) i "3" (w komórce [6,9]) tak więc w komórce [8,9] nie może być tych wartości, więc komórka [8,9] nie ma żadnych możliwych kandydatów - sprzeczność!!! Tak więc wiemy, że wyznaczenie w komórce [1,2] wartości "8" prowadzi do sprzeczności, zatem wykreślając wartość "8" z tej komórki pozostaje nam tylko jeden możliwy kandydat: watrość "5", którą możemy wpisać w nią na stałe!

Czy "Nishio" jest zawsze trudne?

Nie zawsze - ale często! Czasami zobaczysz sprzeczność po kilku posunięciach, a czasami będziesz musiał rozwiązywać sudoku prawie do końca.

Przypominam, że "Nishio" polega na znalezieniu zaprzeczenia i dzięki wyeliminowaniu jednej opcji (kandydata) wstawiamy do komórki startowej drugiego kandydata. Jeśli jednak po wybraniu kandydata w komórce startowej dochodzisz prawie do końca rozwiązywania sudoku i nadal nie widzisz zaprzeczenia możesz być prawie pewien, że wybrałeś poprawnego kandydata dla tej komórki. Jeśli wypełniłeś tylko kilka komórek i zostało jeszcze wiele komórek do ustalenia, więc dalej nie wiesz, czy jest to dobry wybór czy zły. Dobry kandydat nie jest dowodem, a zły jest zaprzeczeniem wyboru!

Porada 1 : Staraj się wybrać taką komórkę startową i takiego kandydata w tej komórce, po którym możesz się spodziewać, że forsownie wymusi on wiele wartości w innych komórkach. Stosując takie podejście, możesz zostać wynagrodzony za swój trud, jeśli dzięki temu dojdziesz do sprzeczności.

Porada 2 : Wybierz trzech lub czterech kandydatów z różnych komórek, następnie wybierz dowolnego z tych kandydatów i utwórz krótki forsowny łańcuch. Jeśli po kilku forsownych posunięciach nie dojdzie do sprzeczności to cofnij wszystkie zmiany jakie dokonałeś po wyborze tego kandydata i wybierz kolejnego z tych trzech / czterech i powtórz czynność. Staraj się zastosować conajmniej kilka takich krótkich łańcuchów (zazwyczaj w którymś z nich dojdzie to sprzeczności) zanim zaczniesz dłuższe i bardziej drobiazgowe poszukiwania.

Porada 3 : Stosuj przeźroczyste nakładki (kalki kreślarskie albo odpowiedniki komputerowe), które naprawdę pomogą ci wypróbować różne łańcuchy bez robienia kompletnego bałaganu w Twoim orginalnym diagramie sudoku!