Encyklopedia Sudoku · Matematyka i informatyka

Matematyka Sudoku

Zaktualizowano 2026-10-05

Kwadrat łaciński z mniejszymi kwadratami

W kwadracie łacińskim każdy symbol występuje raz w każdym wierszu i każdej kolumnie. Wypełniona plansza Sudoku jest kwadratem łacińskim rozmiaru 9 z jednym dodatkowym warunkiem: każdy z dziewięciu kwadratów 3×3 również zawiera każdą cyfrę raz.

Źródła: Wikipedia: Latin square

Ile istnieje siatek

Bertram Felgenhauer i Frazer Jarvis policzyli wypełnione siatki 9×9 w 2005 roku: jest ich 6 670 903 752 021 072 936 960, czyli około 6,67 × 10²¹. Wiele z nich to ta sama siatka w innej postaci. Jeśli dwie siatki uznamy za jedną, gdy jedną można przekształcić w drugą przez zmianę oznaczeń cyfr, obrót, odbicie lub przestawienie wierszy i kolumn w sposób zachowujący poprawność siatki, pozostanie 5 472 730 538 zasadniczo różnych siatek. Liczbę tę obliczyli Ed Russell i Frazer Jarvis.

Źródła: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Minimum 17 wskazówek

Żadne standardowe Sudoku 9×9 z 16 lub mniejszą liczbą danych początkowych nie ma dokładnie jednego rozwiązania. Gary McGuire, Bastian Tugemann i Gilles Civario wykazali to przez wyczerpujące przeszukiwanie komputerowe i ogłosili wynik w styczniu 2012 roku. Siedemnaście to minimum, a nie gwarancja: wiele siatek z 17 danymi początkowymi nadal ma więcej niż jedno rozwiązanie.

Źródła: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Sudoku jako kolorowanie grafów

Narysuj po jednym punkcie dla każdej z 81 komórek i połącz dwa punkty zawsze wtedy, gdy ich komórki znajdują się w tym samym wierszu, tej samej kolumnie lub tym samym kwadracie. Ten graf Sudoku ma 810 połączeń, a każdy punkt ma dokładnie 20 sąsiadów. Rozwiązanie łamigłówki oznacza rozszerzenie kolorowania ustalonego przez dane początkowe tak, aby połączone punkty nigdy nie miały tego samego koloru. Potrzeba co najmniej dziewięciu kolorów, ponieważ każdy wiersz, każda kolumna i każdy kwadrat tworzą grupę dziewięciu punktów, z których każdy jest połączony ze wszystkimi pozostałymi, a dowolna wypełniona siatka pokazuje, że dziewięć kolorów wystarcza.

Źródła: Wikipedia: Sudoku graph

Trudne w ogólności, szybkie dla 9×9

Dla siatek Sudoku, których rozmiar może rosnąć bez ograniczeń (n²×n² z kwadratami n×n), rozstrzygnięcie, czy częściowo wypełnioną siatkę można uzupełnić, jest problemem NP-zupełnym. Wynik ten opublikowali Takayuki Yato i Takahiro Seta w 2003 roku. Wydajne programy komputerowe zazwyczaj rozwiązują zwykłe łamigłówki 9×9 w ułamku sekundy, choć czas zależy od programu, komputera i łamigłówki.

Źródła: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Zobacz także

Źródła

Wszystkie artykuły →