Sciencemag.cz
Doporučujeme
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č.
Tak ako pise autor, aj sudoku pre sudoku.relaxweb.cz a sudoku.relaxweb.sk som generoval obdobnym sposobom (pomocou „riesica“ sudoku)
no backtraking je fakt nejhorší možný způsob … ideální je kombinace s jinými metodami luštění, pak výpočet není tak náročný a dá se poměrně rychle udělat i na počítači přes browser např. http://sudokuzdarma.cz/reseni-sudoku/
Zajímá mě, zda uvedený počet variant sudoku v sobě zahrnuje nebo vylučuje i varianty symetrické, pootočené.
Kolik by bylo variant bez možných symetrií, otáčení, překlápění?
ono v sudoku je i symetrie mezi jednotlivymi cisly. vzdycky lze zamenit vsechny jednicky za vsechny dvojky atd. atd…
Mily Vykouku,
v nultem priblizeni:
otaceni 4x (muze byt brano jako stejne Sudoku). K tomu trivialni preklapeni jen kolem svisle a vodorovne osy jdouci stredem. Takze 3x + jedno zaroven kolem svisle a vodorovne osy.
Otazkou zustava, zda nejake preklapeni (po rotaci) neni shodne s jinou variantou, coz se da lehce vyzkoumat rucne vyzkousenim tech 16 variant.
Opakuji, v nultem priblizeni tedy DELENO 16, protoze trivialnich symetrickych variant je 4×4 tedy 16
Jenze:
=====
a) z MATERSKEHO sudoku dalsi vyrobime libovolnym poradim prvnich tri radku (6x) a k tomu nezavisle libovolnym poradim 4-6 radku (taky 6x) a stejne u poslednich tri radku (take 6x) a stale to bude v podstate to same, i kdyz NEsymetrickych 6x6x6 ruznych variant.
b) Lautr to same po trojicich u sloupcu 6x6x6 dalsich variant
cc) a k tomu varianta a) a po ni b) a porad je to stejne sudoku vytvorene nejakou (Pseudo??)“symetrii“.