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

 

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

Bądź pierwszy!

Powiadom o
avatar
wpDiscuz