Matematycy odkryli zagadkę Sudoku
Naukowcy z University College Dublin mają uspokajające informacje dla wielbicieli Sudoku. Wiedzą już, jak trudna może być ta popularna japońska łamigłówka. Okazuje się, że tabliczka Sudoku musi zawierać co najmniej 17 początkowych cyfr. Jeśli będzie ich mniej, rozwiązanie nie będzie jednoznaczne.
Sudoku stawia przed nami zadanie wypełnienia diagramu 9 na 9 w taki sposób, by w każdym wierszu i kolumnie, a także każdym z dziewięciu pogrubionych bloków 3 na 3 znalazło się po jednej cyfrze od 1 do 9.
Jednoznaczne rozwiązanie łamigłówki
Zadanie jest tym trudniejsze, im mniej początkowych cyfr znajdziemy na diagramie. Przeciętne, gazetowe Sudoku zawiera ich około 25. Do tej pory nie wiadomo było jednak, jaka jest minimalna liczba cyfr, które pozwolą na jednoznaczne rozwiązanie łamigłówki.
Matematycy z Dublina opracowali specjalny algorytm i przez dwa lata testowali możliwe rozwiązania zagadki przy kolejnych liczbach z góry zadanych cyfr.
Trudniejszego się nie da wymyślić
Po uwzględnieniu wszystkich symetrii musieli sprawdzić niespełna 5,5 miliarda kombinacji cyfr, przy czym analiza każdej z nich zajmowała komputerowi z Irish Centre for High-End Computing kilka sekund.
Okazało się, że najmniejszą liczbą cyfr przy której możliwe jest znalezienie tylko jednego rozwiązania jest 17. Nie udało się przy tym znaleźć żadnego układu z 16-ma początkowymi cyframi, który byłby jednoznaczny.
17 to minimum. Trudniejszego Sudoku już wymyślić nie można, choćby nie wiem jak łamać sobie głowę.
