Sudoku: ciekawostka

https://xpil.eu/QJq 📋

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

 

https://xpil.eu/QJq 📋