RMF24 RMF FM RMF MAXX RMF CLASSIC RMF ON
RMF24

Matematycy odkryli zagadkę Sudoku

Autor: Poniedziałek, 9 stycznia 2012 (17:42)

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.

Chcesz widzieć więcej artykułów od RMF24? dodaj w Google

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.

Zadanie jest tym trudniejsze, im mniej poczatkowych 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.

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ę.


Źródło: RMF FM

Najważniejsze Fakty

Zobacz również

Dalsza część artykułu pod materiałem video: