Sudoku: ciekawostka

Technik rozwiązywania Sudoku jest cała chmara. Od najprostszych, typu Naked Single (inaczej: Naked Candidate) czy Single Position, poprzez bardziej zaawansowane typu Naked Pairs czy X-Wings, aż po całkiem egzotyczne typu Forcing Chains czy Nishio. Każdy, kto interesował się kiedykolwiek tematem, zna przynajmniej niektóre z tych nazw, a najtwardsi z Klubu Klozetowych Rozwiązywaczy Sudoku być może nawet próbowali opanować te bardziej skomplikowane.

Tymczasem okazuje się, że z punktu widzenia komputerów istnieje tylko jeden uniwersalny algorytm rozwiązywania łamigłówek Sudoku i w zupełności sprawdza się on dla wszystkich bez wyjątku plansz (nawet tych nieprawidłowych, z wieloma możliwymi rozwiązaniami). Jest to ni mniej ni więcej tylko Random Search. Czyli próbujemy kolejnych cyferek w kolejnych polach, aż trafimy na właściwe rozwiązanie.

Używając wyszukiwania losowego, 99% wszystkich plansz może być rozwiązanych w czasie poniżej jednej dziesiątej sekundy. Sporadycznie trafiają się plansze wymagające czasu w okolicach 1 sekundy. Bardzo, ale to bardzo rzadko trafiają się plansze z czasem rzędu powyżej stu sekund.

Jedyna wymagana do szybkiej pracy algorytmu optymalizacja jest taka, że należy losowe cyferki wybierać zawsze na polach z jak najmniejszą liczbą możliwych kandydatów, co minimalizuje szanse na eksponencjalną “eksplozję” drzewa.

Jeżeli ktoś jest zainteresowany technicznymi szczegółami (w tym również konkretną, bardzo pomysłową i niezwykle krótką implementacją w Pythonie), zapraszam do artykułu autorstwa Petera Norviga (po angielsku): http://norvig.com/sudoku.html

 


Liczba słów w tym wpisie: 255

Sprawdź też

Pchełki Powershell: odzyskujemy klucz aktywacyjny do Windows 10

Niedawno zachciało mi się na jednym z domowych laptopów przetestować Docker for Windows. Niektóre opcje …

Linuks, find, jak pozbyć się komunikatu “Permission denied”

Linuksowa komenda find jest dość potężna: potrafi nie tylko przeszukiwać foldery, ale również wykonywać dowolne …

Zapisz się
Powiadom o
guest
0 komentarzy
Inline Feedbacks
Zobacz wszystkie komentarze
0
Zapraszam do skomentowania wpisu.x
()
x