Trochę statystyk Sudoku

Tradycyjne Sudoku o rozmiarach 9×9 pól to jedna z najpopularniejszych łamigłówek kibelkowych[citation needed]. Dziś odrobina statystyk, bo mi się chwilowo skończyły inne tematy.

  • 6 670 903 752 021 072 936 960 (sześć tryliardów z hakiem, 6.67 x 1021) to całkowita liczba wszystkich możliwych rozwiązań Sudoku (czyli plansz wypełnionych 81 cyferkami).
  • Ponieważ jednak w Sudoku można znaleźć aż 26 różnego rodzaju symetrii, faktyczna liczba łamigłówek, które znacząco różnią się od siebie, wynosi zaledwie – uwaga – 5 472 730 538 (5.47 x 109). Wszystkie pozostałe kombinacje można uzyskać z jednej z tych pięciu miliardów przekształconej przez symetrię (obrót, odbicie, zamianę cyfr, zamianę wierszy lub jakąś inną).
  • Najmniejsza łamigłówka minimalna (tj. taka pozycja startowa, od której nie da się już zabrać żadnej cyfry bez utraty jednoznaczności rozwiązania) musi mieć co najmniej 17 cyfr.
Przykład łamigłówki minimalnej 17-cyfrowej
Przykład łamigłówki 17-cyfrowej z symetrią po przekątnej.
  • Nie udało się ustalić, czy istnieje łamigłówka 17-cyfrowa z podwójną symetrią (tj. względem obydwu przekątnych); najmniejsza taka łamigłówka, jaką udało się dotychczas znaleźć, ma 18 cyfr:
Łamigłówka 18-cyfrowa z podwójną symetrią
  • Dla każdego rozwiązania da się znaleźć łamigłówkę minimalną z nie więcej niż 24 cyframi.
  • Nie wiadomo ile wynosi największa możliwa liczba cyfr łamigłówki minimalnej. Jak na razie udało się znaleźć tylko dwie łamigłówki minimalne 40-cyfrowe. Nie wiadomo czy istnieją większe.
Przykład łamigłówki minimalnej 40-cyfrowej
  • Nie wiadomo dokładnie ile jest wszystkich łamigłówek minimalnych Najlepsze znane obecnie przybliżenie (z dokładnością do około pół promila) to:
    • około 3.1 x 1037 wszystkich łamigłówek minimalnych
    • około 2.55 x 1025 łamigłówek minimalnych po eliminacji symetrii
  • Największy pusty prostokątny obszar na planszy 9×9, dla którego da się ułożyć rozwiązywalną łamigłówkę ma 30 pól (prostokąt 5×6):
Rozwiązywalna łamigłówka z pustym prostokątem 5×6
  • Najmniejsza plansza Sudoku, dla której liczba wszystkich możliwych rozwiązań przekracza liczbę atomów we Wszechświecie to plansza 15×15 pól (podzielona na 15 prostokątów 3×5), dla której istnieje około 3.5 x 1084 poprawnych rozwiązań.

Dzisiejszy wpis jest skompresowanym wyciągiem z tego artykułu. Polecam lekturę – jest tam mnóstwo interesujących klamotów o metodach liczenia tych wszystkich wielkich liczb, o innych wariantach gry oraz sporo ciekawych odnośników do innych stron o Sudoku jakby komuś było za mało 😉

Zapisz się
Powiadom o
guest
4 komentarzy
Inline Feedbacks
Zobacz wszystkie komentarze
4
0
Zapraszam do skomentowania wpisu.x
()
x