email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Zgadywanie (Guessing)

Jeśli wypróbowałeś wszystkie znane ci metody rozwiązywania oraz kilka szybkich prób Nishio nie posunęło cię dalej, więc może potrzebujesz "zgadywania". Większość zadań sudoku nie wymaga zgadywania; być może jest jeszcze jakaś logiczna metoda, której nie użyłeś albo zagadka sudoku, która ci się trafiła naprawdę wymaga zgadywania!

Po pierwsze, jeśli musisz zgadywać wybierz taką komórkę startową, która ma niewielu kandydatów, a wybór jednego z nich (ustalenie, że komórka startowa ma wartość tego właśnie kandydata) pozwoli ci na forsowanie wartości w wielu następnych komórkach.

Następnie musisz mieć świadomość, że po wyborze komórki startowej i kandydata przed tobą bardzo dużo pracy zanim dojdziesz do końca (rozwiążesz prawidłowo sudoku lub wybrany kandydat okaże się zły, bo doprowadza do sprzeczności).

Na konieć najgorsza część - jedno zgadywanie może nie wystarczyć! Jest możliwe, że wzdłuż trasy uzupełniania sudoku będziesz musiał zrobić kilka zagnieżdżonych zgadywań. Każde będzie prowadzić cię dalej inną ścieżką z odmiennymi wyborami. Koniecznie zaopatrz się w gumkę!

Jeśli twoje zadanie wymaga zagnieżdzonych zgadywań możliwe są następujące scenariusze:
1-szy: po wyborze komórki startowej i kandydata z tej komórki forsownie wyznaczasz wartości następnych komórek aż dojdziesz do martwego punktu - dalej nie da się już wyznaczyć następnych komórek i trzeba następnego zgadywania - kolejnej komórki startowej i testować kolejnych kandydatów tej komórki startowej.
2-gi : dojdziesz do sprzeczności i będziesz musiał wrócić do ostatniego punktu zgadywania (przywrócić z powrotem wszystkie zmiany od ostatniego zgadywania i wybrać innego kadydata z komórki startowej. Jeśli wszyscy kandydaci zostali przetestowani z danej komórki startowej to musisz wrócić do poprzedniego punktu zgadywania i wybrać innego kandydata.
3-ci : rozwiążesz poprawnie tą zagadkę sudoku, więc możesz wpisać na stałe wartości tymczasowo naniesione w komórkach.
Dlatego technika bazująca na zgadywaniu i wykorzystująca technikę Nishio zwana jest "siecią Ariadny". Postępując w ten sposób dojdziesz w końcu do poprawnego rozwiązania sudoku (o ile dane zadanie ma poprawne rozwiązanie), ale zabierze ci to bardzo dużo czasu (o wiele łatwiej jest korzystać z logicznych technik, o ile to możliwe).
Ariadna była córką króla Krety Minosa, która pomogła Tezeuszowi dając mu miecz do zabicia minotaura i sieć, by pomogła mu wydostać się z powrotem z labiryntu. Tezeusz przymocował sieć do pewnego punktu w labiryńcie, a następnie po dojściu do martwego punktu zwijał sieć z powrotem i obierał inną drogę.

Technika Zgadywania (zwana też techniką Prób i Błędów) jest znana jako ROZWIDLENIE - wiele programów komputerowych do rozwiązywania sudoku wykorzystuje tylko tą technikę. To może wydawać się dziwne, ale jest to bardzo proste dla programów komputerowych by sprawdzić wszystkie przypuszczenia w celu skompletowania zagadki sudoku i trywialne by cofnąć się do poprzedniego wyboru. Ludzie nie pracują w ten sposób! (ale przecież potrafimy myśleć logicznie, dedukować - czego komputery nie potrafią - jeszcze!)