Matematycy rozwiązali odwieczny sekret sudoku

Sudoku to doskonale chyba wszystkim znana liczbowa krzyżówka. Aż do teraz jednak kryła ona pewien nierozwiązany problem. Problem, który udało się rozgryźć matematykom przy wykorzystaniu współczesnego superkomputera.

Sudoku składa się z pól 9 na 9 kratek, które są podzielone na jeszcze mniejsze kwadraty - 3 na 3 kratki. W każdym z nich, oraz w każdym rzędzie i kolumnie musi się znaleźć każda cyfra od 1 do 9. Jest jeszcze jedna ważna zasada - każda krzyżówka musi mieć tylko jedno właściwe rozwiązanie. Dlatego konieczna jest pewna ilość wskazówek - odkrytych pól - na starcie.

Miłośnikom tego typu krzyżówek udało się okryć, że minimalna liczba takich odkrytych pól wynosi 17. Nie udało się nigdy stworzyć sudoku z 16 lub mniej odkrytymi polami, które dałoby się rozwiązać tylko w jeden sposób. Jednak czy faktycznie (i dlaczego) tak jest, pozostawało do dziś wielką matematyczną zagadką.

Dlatego do akcji wkroczyli tu naukowcy z University College Dublin, którzy stworzyli program nazwany Checker, który następnie odpalili na maszynie składającej się z 640 sześciordzeniowych procesorów Intel Xeon.

Program ten miał bardzo proste zadanie. Musiał on sprawdzić każde możliwe rozwiązanie dla każdego możliwego sudoku!

Liczba uzyskanych kombinacji była zatrważająca - wyniosła ona 6670903752021072926960 (ok. 10^21). Jednak część z nich można było wykluczyć biorąc pod uwagę symetrię. Dlatego do sprawdzenia pozostało "zaledwie" 5472730538 możliwych kombinacji.

Jednak sam proces sprawdzania jednej, pojedynczej krzyżówki jest skomplikowany. Dla każdej z nich istnieje około 10^16 podpowiedzi składających się z 16 odkrytych pól. Jednak znowu okazało się, że niektóre z nich można wyeliminować, gdyż są one a przykład lustrzanymi odbiciami innych.

Mimo tego liczba obliczeń była przeogromna. Zajęło to komputerowi 7.1 miliona godzin czasu procesora - w czasie rzeczywistym cały proces trwał od stycznia, a zakończył w grudniu.

Oczywiście za wszystkim nie stała tylko zabawa i dobre samopoczucie miłośników sudoku. Obliczanie możliwych kombinacji sudoku jest praktycznie identyczne z obliczeniami występującymi przy ekspresji informacji genetycznej czy też w złożonych sieciach komputerowych. Uzyskane więc metody szybszych obliczeń będzie można także wykorzystać w tych dziedzinach.

Przy tym problem minimalnej ilości podpowiedzi w sudoku nie został do końca rozwiązany. Nadal nie ma zgrabnego dowodu pokazującego dlaczego właśnie minimalna liczba odkrytych pól to właśnie 17.

Źródło: