Encyklopedie sudoku · Matematika a výpočetní technika

Matematika sudoku

Aktualizováno 2026-10-05

Latinský čtverec s bloky

V latinském čtverci se každý symbol vyskytuje právě jednou v každém řádku a každém sloupci. Vyřešené sudoku je latinský čtverec řádu 9 s jednou podmínkou navíc: také každý z devíti bloků 3×3 obsahuje každou číslici právě jednou.

Zdroje: Wikipedia: Latin square

Kolik existuje mřížek

Bertram Felgenhauer a Frazer Jarvis v roce 2005 spočítali vyplněné mřížky 9×9: je jich 6 670 903 752 021 072 936 960, přibližně 6,67 × 10²¹. Mnohé z nich jsou stejnou mřížkou v jiné podobě. Pokud dvě mřížky počítáme jako jednu vždy, když lze jednu převést na druhou přeznačením číslic, otočením nebo zrcadlením či přeuspořádáním řádků a sloupců způsoby, které zachovávají platnost mřížky, zbývá 5 472 730 538 v zásadě odlišných mřížek. Tento počet vypočítali Ed Russell a Frazer Jarvis.

Zdroje: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Minimum 17 zadaných číslic

Žádné standardní sudoku 9×9 s 16 nebo méně zadanými číslicemi nemá právě jedno řešení. Gary McGuire, Bastian Tugemann a Gilles Civario to prokázali vyčerpávajícím počítačovým prohledáváním a výsledek oznámili v lednu 2012. Sedmnáct je minimum, nikoli záruka: mnoho mřížek se 17 zadanými číslicemi má stále více než jedno řešení.

Zdroje: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Sudoku jako barvení grafů

Nakreslete jeden vrchol pro každou z 81 buněk a spojte dva vrcholy vždy, když jejich buňky sdílejí řádek, sloupec nebo blok. Tento graf sudoku má 810 hran a každý vrchol má právě 20 sousedů. Řešení hlavolamu znamená rozšířit obarvení určené zadanými číslicemi tak, aby spojené vrcholy nikdy neměly stejnou barvu. Je potřeba alespoň devět barev, protože každý řádek, sloupec a blok tvoří skupinu devíti vrcholů, které jsou všechny navzájem propojené, a každá vyplněná mřížka ukazuje, že devět barev stačí.

Zdroje: Wikipedia: Sudoku graph

Obecně obtížné, pro 9×9 rychlé

U mřížek sudoku, jejichž velikost může neomezeně růst (n²×n² s bloky n×n), je rozhodnutí, zda lze částečně vyplněnou mřížku dokončit, NP-úplným problémem. Tento výsledek publikovali Takayuki Yato a Takahiro Seta v roce 2003. Efektivní počítačové programy obvykle vyřeší běžné hlavolamy 9×9 za zlomek sekundy, doba však závisí na programu, počítači a hlavolamu.

Zdroje: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Viz také

Zdroje

Všechny články →