Encyklopédia sudoku · Matematika a počítače

Matematika sudoku

Aktualizované 2026-10-05

Latinský štvorec s blokmi

V latinskom štvorci sa každý symbol objavuje raz v každom riadku a v každom stĺpci. Hotové sudoku je latinský štvorec veľkosti 9 s jednou podmienkou navyše: aj každý z deviatich blokov 3×3 obsahuje každú číslicu raz.

Zdroje: Wikipedia: Latin square

Koľko mriežok existuje

Bertram Felgenhauer a Frazer Jarvis v roku 2005 spočítali hotové mriežky 9×9: je ich 6 670 903 752 021 072 936 960, teda približne 6,67 × 10²¹. Mnohé z nich sú tá istá mriežka v prestrojení. Ak budete dve mriežky počítať ako jednu vždy, keď sa jedna dá zmeniť na druhú zámenou číslic, otočením alebo zrkadlením či preusporiadaním riadkov a stĺpcov spôsobmi, pri ktorých mriežka ostáva platná, dostanete 5 472 730 538 v podstate rôznych mriežok; toto číslo 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 čísel

Žiadne štandardné sudoku 9×9 so 16 alebo menej zadanými číslami nemá práve jedno riešenie. Gary McGuire, Bastian Tugemann a Gilles Civario to ukázali úplným počítačovým prehľadávaním a výsledok oznámili v januári 2012. Sedemnásť je minimum, nie záruka: mnohé mriežky so 17 zadanými číslami majú stále viac ako jedno riešenie.

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

Sudoku ako farbenie grafu

Nakreslite jeden bod za každú z 81 buniek a spojte dva body vždy, keď ich bunky ležia v tom istom riadku, stĺpci alebo bloku. Tento graf sudoku má 810 spojení a každý bod má presne 20 susedov. Vyriešiť hlavolam znamená rozšíriť farby určené zadanými číslami tak, aby spojené body nikdy nemali rovnakú farbu. Potrebných je aspoň deväť farieb, pretože každý riadok, stĺpec a blok je skupina deviatich bodov, ktoré sú všetky navzájom spojené, a každá hotová mriežka ukazuje, že deväť farieb stačí.

Zdroje: Wikipedia: Sudoku graph

Vo všeobecnosti ťažké, pri 9×9 rýchle

Pri mriežkach sudoku, ktoré môžu neobmedzene rásť (n²×n² s blokmi n×n), je rozhodnutie, či sa dá čiastočne vyplnená mriežka dokončiť, NP-úplný problém; tento výsledok publikovali Takayuki Yato a Takahiro Seta v roku 2003. Efektívne počítačové programy zvyčajne vyriešia bežné hlavolamy 9×9 za zlomok sekundy, hoci čas závisí od programu, počítača a hlavolamu.

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

Pozri aj

Zdroje

Všetky články →