Matematyka Sudoku prowadzi do „Skali Richtera” twardości puzzli

Globalna fascynacja Sudoku doprowadziła do nagłego zainteresowania matematycznymi właściwościami układanki. W ciągu ostatnich kilku miesięcy na tym blogu przyjrzeliśmy się, jak matematycy rozwiązali problem minimalnego Sudoku, a nawet jak wykorzystali matematykę Sudoku do szyfrowania obrazów .

Dziś mamy inne podejście do Sudoku dzięki pracy Marii Ercsey-Ravasz z Uniwersytetu Babes-Bolyai w Rumunii i Zoltana Toroczkai z Uniwersytetu Notre Dame w Indianie.

Ci faceci opracowali sposób mierzenia trudności konkretnej łamigłówki Sudoku i twierdzą, że ich skala trudności łamigłówek Richtera może być zastosowana w wielu innych grach.

Najpierw krótkie wprowadzenie do Sudoku. Jest to łamigłówka liczbowa składająca się z siatki 9 x 9, w której niektóre komórki zawierają wskazówki w postaci cyfr od 1 do 9. Zadaniem rozwiązującego jest wypełnienie pozostałych komórek tak, aby każdy wiersz, kolumna i pole 3×3 były siatka zawiera wszystkie dziewięć cyfr. Dodatkowo każda siatka może mieć tylko jedno rozwiązanie.

Łamigłówki Sudoku są ogólnie klasyfikowane jako łatwe, średnie lub trudne, przy czym łamigłówki mają więcej wskazówek na początek, ale nie zawsze są łatwiejsze do rozwiązania. Ale matematyczne obliczenie trudności jest trudne.

Teraz Ercsey-Ravasz i Toroczkai twierdzą, że opracowali sposób na zrobienie tego za pomocą algorytmicznej teorii złożoności. Wskazują, że łatwo jest zaprojektować algorytm, który rozwiązuje Sudoku, testując każdą kombinację cyfr, aby znaleźć tę, która działa. Tego rodzaju brutalne rozwiązanie gwarantuje odpowiedź, ale niezbyt szybko.

Zamiast tego projektanci algorytmów szukają sprytniejszych sposobów znajdowania rozwiązań, które wykorzystują strukturę i ograniczenia problemu. Te algorytmy i ich zachowanie są bardziej złożone, ale szybciej uzyskują odpowiedź.

Centralnym punktem argumentacji Ercseya-Ravasza i Toroczkai jest to, że ponieważ algorytm odzwierciedla strukturę problemu, jego zachowanie – zwroty akcji, którymi podąża w przestrzeni stanów – jest dobrą miarą trudności problemu.

Aby to zademonstrować, posługują się przykładem Sudoku. Zamiast metody brutalnej opracowali znacznie bardziej elegancki algorytm, który wykorzystuje różne ograniczenia układanki, takie jak fakt, że każda kolumna i podsiatka wiersza musi zawierać wszystkie cyfry od 1 do 9.

W ten sposób przekształcają problem w typ znany teoretykom złożoności jako problem k-sat.

Zaczynają od wstawienia losowego zestawu liczb do siatki i podążają za trajektorią algorytmu w przestrzeni stanów, szukając rozwiązania. W przypadku prostego problemu, ta trajektoria jest prosta, jak pokazano na górze z dwóch liczb na górze tego postu.

Ale wszystko to zmienia się w trudny problem. Ercsey-Ravasz i Toroczkai testują swój algorytm na siatce Sudoku tak mocno, że ma ona swoją własną nazwę: platynowy blond. Wynik jest pokazany w dolnej połowie rysunku. Jest znacznie bardziej złożony, a jego rozwiązanie zajmuje dziesięć razy więcej czasu.

Ercsey-Ravasz i Toroczkai twierdzą, że w przypadku trudnych problemów trajektoria staje się chaotyczna, zanim zdecyduje się na rozwiązanie. W rzeczywistości czas potrzebny na wydostanie się z tego chaotycznego stanu jest prostą miarą trudności.

Na tej podstawie tworzą „skalę Richtera” trudności łamigłówki opartą na współczynniku ucieczki. Skala wynosi od 1 do 4, przy czym jeden oznacza najłatwiejszy, a 4 ultratwardy.

Mówią, że ta skala zaskakująco dobrze koreluje z subiektywnymi ocenami ludzi, gdzie 1 odpowiada łatwym zagadkom, 2 - średnim zagadkom, a 3 - trudnym zagadkom. Platynowy blondyn ma trudność 3,5789.

Ciekawym wnioskiem jest to, że żadna łamigłówka Sudoku nie jest znana o stopniu trudności 4. A liczba wskazówek również nie zawsze jest dobrą miarą trudności. Ercsey-Ravasz i Toroczkai twierdzą, że przetestowali wiele łamigłówek, w tym kilka z 17 wskazówkami, minimalną liczbą i kilka z 18 wskazówkami.

Wszystkie były łatwiejsze do rozwiązania niż platynowy blond, który ma 21 wskazówek. Dzieje się tak, ponieważ twardość łamigłówki zależy nie tylko od liczby wskazówek, ale także od ich pozycji.

Ciekawym pytaniem jest teraz, czy naprawdę istnieje ultratrudna łamigłówka o stopniu trudności 4 i jak ją znaleźć.

Co ważniejsze, metoda Ercsey-Ravasz i Toroczkai uogólnia wszystkie problemy k-sat tej samej klasy co Sudoku. Tak więc trudność tych problemów można sklasyfikować za pomocą podobnych skal typu Richtera.

Pozostaje tylko jedno pytanie – jak nazwać skalę trudności łamigłówki? Oczywistą odpowiedzią jest skala Ercsey-Ravasz i Toroczkai lub skala ERT. Wszelkie inne sugestie w sekcji komentarzy poniżej.

Nr ref.: arxiv.org/abs/1208.0370 : Chaos w Sudoku

ukryć