Matematika za sudoku

Doporučujeme

Webbův dalekohled objevil velké množství plynů bohatých na uhlík, které slouží jako ingredience pro budoucí planety

21. 11. 2024

Editování genů CRISPR/Cas9 vedlo k zefektivnění fotosyntézy

20. 11. 2024

Týden na ITBiz: Pomocí DNA vyrobili diamantové fotonické krystaly

19. 11. 2024

Víme, kolik minimálně číslic musí být předvyplněno, aby sudoku mělo jednoznačné řešení? Jaká je výpočetní náročnost úlohy, jak fungují programy na řešení i generování úloh?

Na naše otázky odpovídá Robert Babilon. Vystudoval Matematicko-fyzikální fakultu Univerzity Karlovy v Praze, po studiu tam krátce pracoval v Institutu teoretické informatiky. Poté přešel do praxe a živí se jako programátor, zejména v oblasti dopravy. Několikrát se zúčastnil mistrovství světa v sudoku, odkud si přivezl jednu bronzovou medaili v soutěži jednotlivců a dvě medaile (stříbrnou a bronzovou) jako člen českého týmu.

Sudoku je dnes celosvětově nejoblíbenější logická úloha. Oblibu si získalo zejména díky jednoduchým pravidlům (srovnejte se šachy), široké škále obtížnosti i univerzálností (na rozdíl od doplňovaček slov není vázáno na konkrétní jazyk).
Rychlému rozvoji pomohla možnost generovat úlohy pomocí počítačových programů, což umožnilo vydavatelům výrazně ušetřit na autorských honorářích.
V dalším textu se budeme zabývat, pokud nebude uvedeno jinak, klasickým sudoku 9×9 rozděleným do čtverců 3×3. Existuje mnoho dalších různých variant, ať už se liší svými rozměry, nepravidelným rozdělením na oblasti či dalšími podmínkami (sudé/liché, diagonální, sudoku kombinované s kakurem, tedy se součty číslic…).

Jak obtížné je luštění sudoku z pohledu počítačových programů?

Otázka obtížnosti je u klasického sudoku 9×9 pro matematika poněkud neuchopitelná, protože existuje jenom konečný počet zadání. Matematici klasifikují algoritmy podle toho, jak roste časová náročnost s velikostí zadání. V roce 2002 ukázali Japonci Yato a Seta (připomeňme si, že v té době sudoku mimo Japonsko v podstatě ještě nebylo známo), že úloha vyřešit sudoku N×N je tzv. NP-úplná. Jinak řečeno, doba potřebná k řešení s růstem vstupu roste pravděpodobně exponenciálně. (Ve skutečnosti zatím nikdo nedokázal, že ten růst je opravdu exponenciální. Nicméně, kdyby někdo našel polynomiálně rychlý algoritmus pro řešení sudoku, vyřešil by tím jednu ze zásadních otázek matematické kombinatoriky a stal by se jedním z nejslavnějších matematiků.)

Onen konečný počet různých kompletně vyplněných tabulek je mimochodem znám?

Úlohou se zabývali na univerzitě v Sheffieldu a v roce 2003 (tj. ještě před celosvětovým rozšířením sudoku, k němuž došlo v roce 2005) dospěli k číslu 6670903752021072936960. Finální výpočet trval tehdy na jednom běžném PC méně než sekundu. Pro ukázku toho, jak je exponenciální nárůst drsný – výpočet počtu kombinací pro sudoku 12×12 rozdělené na obdélníky 4×3 zabral více než 3 měsíce, přičemž byl rozdělen paralelně na několik počítačů.

Kolik minimálně políček musí být zadáno, aby úloha měla jednoznačné řešení?

Tato otázka trápila matematiky a programátory delší dobu. Tvůrcům sudoku se dařilo vytvářet úlohy se 17 zadanými čísly a jednoznačným řešením, některé luštitelské časopisy dokonce mají rubriku Sudoku17 s takovými úlohami. Tušilo se, že 16 předvyplněných čísel asi nemůže stačit, nicméně důkaz se podařil teprve nedávno, v roce 2012. Zde stojí za to podotknout, že samotný počet zadaných čísel nemusí korelovat s obtížností úlohy. Existují úlohy se 17 zadanými čísly, které zvládne i amatérský luštitel a jsou úlohy s více než polovinou zadaných čísel (mřížka má celkem 81 čísel, takže 42 a více čísel), které nejsou v rozumném čase luštitelné ani pro mistra světa.

Co zajímavého lze říct o sudoku z pohledu programátorského?

Tady bych rozlišil tvorbu úloh a jejich luštění. Úlohy se strojově tvoří zpravidla tak, že se vytvoří náhodná kompletně vyplněná tabulka a postupně se odmazávají čísla tak dlouho, dokud nedostaneme úlohu požadované obtížnosti a stále jednoznačně řešitelnou. Jak je tedy vidět, každý program pro tvorbu sudoku je musí umět i řešit.
K řešení se dá přistupovat různými způsoby – buďto čistě hrubou silou (backtrackingem, tj. postupným zkoušením všech možností políčko po políčku), nebo napodobováním lidských postupů, anebo nejčastěji kombinací obojího. Většinou chceme spolu s důkazem jednoznačnosti řešení (tedy správnosti zadání) získat i nějakou představu o obtížnosti úlohy, tak se čistě hrubá síla moc nehodí. Navíc hrozí, že některé úlohy takto v rozumném čase vůbec nevyřešíme. Proto je potřeba, aby program využíval alespoň základní „lidský“ postup – pokud najdu řádek, sloupec nebo čtverec, ve kterém existuje pro nějaké číslo poslední možnost, tak ho tam vepíšu. Zkoušel jsem tento princip kombinovaný s backtrackingem na úlohy, o kterých autoři tvrdí, že jsou nejtěžší na světě (kdekdo se domnívá, že právě ta jeho úloha je zrovna nejtěžší), a vždy se ji povedlo vyřešit do 10 sekund. Jak je vidět, rozměr 9×9 je ideální nejen pro člověka, ale i pro počítač.