Jak se matematika a počítače noří do světa sudoku

Pavel Houser , 20. srpen 2015 09:15 2 komentářů
Rubriky: Science
Jak se matematika a počítače noří do světa sudoku

Mánie kolem sudoku začala v západním světě v Británii na přelomu let 2004-2005. ČR nebyla dlouho pozadu, v novinách zde vycházejí tyto hádanky již od roku 2005, ve stejné době se objevily i sbírky úloh a on-line aplikace.

Móda na dlouho

V roce 2006 to na západ od nás chvíli vypadalo, že podobně se rozšíří další podobná hra, kakuro, ta však v ČR srovnatelné popularity nikdy nedosáhla a móda ustoupila i na západ od nás – doplňovat číslice je prostě přitažlivější než kombinovat v hlavě často dlouhé součty. Sudoku však, ačkoliv se považovalo za módní vlnu, přetrvalo (třeba ve srovnání s Rubikovou kostkou). V minulosti mívaly seriózní noviny šachovou rubriky, dnes místo šachových diagramů (ale i křížovek) vystřídalo sudoku. A plným právem, tato hra je geniální v tom, že kombinuje různě obtížné, často i velmi sofistikované operace, s velmi jednoduchými základními pravidly. Srovnejte to s šachy, kde něco samostatně vymyslet a ocenit určitou estetiku vyžaduje docela dost času, zvládnout pohyby figur, základy strategie, propočtu... (Navíc sudoku nepotřebuje protihráčce, ale to šachová úloha ani křížovka také ne.). V národnostně i jinak promíchané Británii a dalších zemích je velkou výhodou sudoku také univerzálnost čísel, hra je tedy nezávislá na jazyku, vzdělání i kulturním zázemí. (Někdy se sudoku i v tomto přirovnává k Rubikově kostce, ale to podle mého názoru zase úplně míjí rozdílnost metod řešení; téměř určitě se při tom budou primárně namáhat různé oblasti mozku.)

Zajímavé ovšem je, že na to, jak je hra jednoduchá, si s ní matematika ani hrubá či jemnější síla počítačových programů ještě zdaleka neví beze zbytku rady. I to svědčí o tom, to není žádná trivialita. K sestavování úloh, kontrole zadání i luštění se programy samozřejmě používají od počátku. Existuje řada efektních demonstrací, Google třeba předvedl, jak sudoku řeší mobilní telefon pouhým zaměřením úlohy fotoaparátem (při demonstraci v roce 2010 samotný výpočet probíhal na serveru/cloudu, dneska jsou už i aplikace pro Android a výkon mobilních zařízení by to měl zvládnout i lokálně; platí to i pro ultatěžká zadání?). Vzhledem k popularitě hry se jí prostě zabývá řada matematiků i programátorů, i v Čr se tomu věnuje řada matematických diplomek, stačí trochu hledat, svá tajemství sudoku ovšem bezezbytku nevydalo.

16, nebo 17 číslic?

Začněme třeba tím, kolik sudoku může existovat (následující čísla viz Alex Bellos: Alexova dobrodružství v zemi čísel, české vydání Dokořán 2015). Vyplněných zadání je 6 670 903 752 021 072 963 960, tento počet ovšem můžeme snížit, pokud za stejnou úlohu budeme považovat řešení vůči sobě nějak symetrická (otočení, plošná záměna jedné číslice za druhou...), ovšem zvyšuje se zase počtem zadání. K číslu se dospěje poměrně komplikovaným a ne zrovna elegantním způsobem. Začneme tím, že sudoku je magický čtverec 9 x 9 (ani zde ale není vzorec zrovna intuitivní) a pak se přidávají omezující podmínky, tj. zákaz opakování číslic i ve čtverečcích 3 x 3; nicméně i v diplomkách na toto téma bývá postup pro jeho komplikovanost jen naznačen.

Za zadání samozřejmě považujeme jen mřížku předvyplněnou tak, aby úloha měla řešení, a to jednoznačné. Je jasné, že pro prázdnou mřížku bude existovat rozhodně ne jedno řešení, ale onen počet výše. Asi nejvíce přitahuje teoretiky otázka, jaký je nejmenší počet číslic, abychom mohli úlohu ještě vůbec sestavit (naopak je to mnohem méně zajímavé, protože už 4 prázdná políčka 2 x 2 v rohu a 2 x 2 chybějící číslice znamenají neexistenci jednoznačného řešení). Nepodařilo se sestavit zadání sudoku, které by v mřížce mělo méně než 17 předvyplněných číslic. Úloh se 17 číslicemi je známo několik desítek tisíc – počítáno opět po očesání symetrií.

Hrubá síla výpočtů, triky programátorů ani um matematiků zatím nicméně nestačil ani na důkaz, kolik je 17číslicových úloh – můžeme poznat, že už jsme objevili všechny? A už vůbec není znám důkaz, že se 16 číslicemi žádné sudoku sestavit nejde. Nikdo nepředložil ani nějaký obecný přístup k problému, pokud tedy vůbec existuje (vzpomeňme na to, že hrubou silou byl ke zklamání části matematiků vyřešen už tzv. problém čtyř barev, tedy zda lze čtyřmi barvami vybarvit libovolnou mapu bez toho, aby se spolu plochy/země obarvené stejnou barvou dotkly jinak než v bodě; zklamání pocházelo z toho, že se nenašel žádný elegantní princip, který by byl srozumitelný člověku, nebo alespoň matematikovi; samotný důkaz je počítačový, řekne se, že veškeré mapy patří k několika tisícům typů konfigurací a ty se pak proberou zvlášť). Třeba Gordon Royle z University of West Australia ukazuje, jak matematikové v problému 16číslicových sudoku spíše tápou. Tvrdí, že podle něj takovou úlohu nepůjde sestavit – a to jen na základě intuitivního argumentu, že známe desetitisíce 17číslocových úloh. Kdyby existovala i řešení s 16 číslicemi v zadání, na nějaké bychom přišli pokusným odebíráním číslic ze známých úloh o 17. Podle jiných zdrojů to, že 17 číslic je minimum, je prý dokázáno, důkaz ale nikde není, čili tomu těžko věřit.

Osobní zkušenosti

Obtížnost úlohy však nutně nesouvisí s počtem předvyplněných čísel. Když budete hledat „nejtěžší sudoku“, klidně najdete i zadání s 20 předvyplnenými číslicemi. Na pohled zde nebude vidět, jak vyplnit byť jen jediné číslo, ani jak „vytvořit spor“ (tím myslím představovat si třeba postupně doplňovanou číslici, až se dojde ke sporu, a na tomto základě vyloučíme i vyplnění pole, kde to na první pohled není vidět). Předpokládám, že půjde o typ úloh, kde už žádnou číslici odebrat nejde, protože by už jednoznačné řešení neexistovalo – tohle ověřit by už algoritmy měly umět.

Jinak subjektivně obtížnost úloh závisí na lecčems: někomu se lépe luští, když se např. může rozjet, tj. první čísla lze doplnit snadno a na lámání chleba dojde až později. Někteří lidé dokonce reportují, že jim není ani jedno, jaké číslice jsou předvyplněny, dejme tomu se cítí lépe, když před sebou vidí více osmiček než sedmiček. Je to možné?

(Poznámka: Moje zkušenost se sudoku je ovlivněna asi trochu specifickým přístupem: neřeším na čas, ale zato si nepíšu do mřížky možnosti, nevracím se „gumováním“, ale vždy doplňuji číslici až ve chvíli, si v hlavě propočtu, že jinak to nelze. Asi jako tah v šachách je také závazný, nedá se vracet a nelze na umístit dvě figurky na dvě pole v „superpozici“ ani během hry pohybovat figurkami na šachovnici sem a tam na zkoušku.)


Komentáře

Jan Novák #0
Jan Novák 28. srpen 2015 15:18

Sudoku je taková dobrá hříčka, ale osobně mám raději křížovky nebo osmisměrky.
Pokud by se mělo hledat, kolik existuje sudoku, tak bych to viděl tak, že do prvního čverce by se vyplnilo všech 9 číslic a zjistil by se počet platných kombinací (všechny ostatní by byly permutacemi kdy by se symboly 1-9 nahrazovaly jinými symboly třeba 1-9 ale v jiném pořadí). Samozřejmě když jsem tohle vyzkoušel hrubou silou (mým programem na nalezení řešení sudoku), musel jsem toho asi po hodině nechat. A když vidím to dlouhé číslo, tak i po vydělení počtem permutací (tedy ubráním tak pěti míst) je to furt moc.
Řešení sudoku v počítači je sice dobré na machrování, ale neni to taková zábava. Sám jsem dělal několik programů na různých principech. První program hledal jaká čísla lze do okénka vypsat a v další verzi pokud byla jediná možnost tak ji tam napsal (třetí verze pak tento postup opakovala dokud bylo co vyplňovat). Už tady jsem narazil, protože ne všechna sudoku (dokonce i některá označovaná jako jednoduchá) mají takto přímočaré řešení. Další postup jsem už neprogramoval (např. dvojka bude buď tady nebo tady, ale na jediném řádku a tedy v jiném čtverci na tomto řádku být nemůže - tuto jednoduchou úvahu neuměl a dosud neumí a asi nikdy umět nebude, protože pochybuju, že se k němu vrátím). Zkoušel jsem čtvrtou verzi, která vzala políčko s nejméně možnostmi (obvykle dvěma) a ty měla postupně otestovat. To jsem ale už nedodělal, protože jsem měl jiné úkoly, než si hrát se sudoku. Na reakci toho, že program občas skončil jakýmsi patem - vyplňoval jenom tam kde to jednoznačně šlo a přesto se dostal do situace, že mu někde vyšlo 0 možností (asi vadné sudoku, ale to by se to nesmělo stávat tak často - uvěřit, že 5% sudoku je vadných nechci), jsem to vzal za jiný konec. Udělal jsem úplně jiný program, dokonce v jiném jazyce. Tento program řešil sudoku hrubou silou a to tak, že do prvního prázdného políčka postupně testoval všechna čísla, splňující podmínky a takto upravené ho předával k dalšímu řešení a toto se rekurzivně opakovalo tolikrát, dokud to šlo (tj. dokud se nenalezlo řešení nebo dokud bylo možné bez porušení pravidel nějaké číslo do následujícího plíčka doplnit). Ačkoliv to zní složitě, program pracoval velice rychle (do několika sekund vyřešeno) a těch pokusů (slepé vyplňování čísel, které neskončilo řešením) bylo řádově jen několik tisíc (ovšem že jsem je počítal, stejně jako hloubku rekurze, u které mi později došlo, že musí být stejná jako počet prázdných okének). Tento progam tedy našel všechna řešení (obvykle bylo jedno), takže kdyby se stalo, že zadání není jednoznačné, najde všechny (pokud si na tom nevyláme zuby jako v případě, který popisuju na začátku).

milan #1
milan 04. září 2015 20:09

No to se dalo čekat. Naco luštit Sudoku, když si na to múžeš vymyslet program... A když ani zdaleka nejsi na stopě, tak sudoku nazveš hříčkou

RSS 

Komentujeme

Další na řadě je bezpečnost

Richard Jan Voigts , 09. říjen 2017 00:00
Richard Jan Voigts

Co všechno lze automatizovat pomocí strojového učení? Larry Ellison, technologický ředitel společnos...

Více







Kalendář

19. 10.

22. 10.
For Games 2017
24. 10. VeeamON Forum 2017
25. 10.

26. 10.
Profesia days 2017
RSS 

Zprávičky

ČSÚ: Volební weby byly nedostupné kvůli útoku DDoS

Pavel Houser , 22. říjen 2017 17:43

Výpadky prezentačních server vznikly na straně externího dodavatele komunikačních služeb. ...

Více 0 komentářů

Úřad pro ochranu osobních údajů vyšetřuje e-shop Mall.cz kvůli úniku hesel

ČTK , 22. říjen 2017 08:00

Obchodu Mall.cz odcizili hackeři údaje až ke 750 000 starších uživatelských účtů....

Více 0 komentářů

Firma vypsala odměnu za odhalení digitálního podpisu slovenského ministra

ČTK , 21. říjen 2017 08:00

Problém se týká čipů německého výrobce Infineon Technologies, které Slovensko používá v občanských p...

Více 0 komentářů

Starší zprávičky

Electro World v účetním roce zmírnil ztrátu na 92 milionů Kč

ČTK , 20. říjen 2017 12:00

Firma se soustředila na zlepšení prodejní a distribuční sítě a rozšíření sortimentu....

Více 0 komentářů

Dohoda o ochraně dat mezi EU a USA prošla první kontrolou

ČTK , 20. říjen 2017 08:00

Cílem dohody je chránit osobní údaje osob v EU předávané společnostem v USA. ...

Více 0 komentářů

Operátoři: Metro by mohlo být signálem pokryté do konce roku 2018

ČTK , 20. říjen 2017 08:00

Operátoři mají enormní zájem na pokrytí pražského metra, a to na vlastní náklady....

Více 0 komentářů

Firmu Moravia IT koupil britský konkurent RWS Holding

ČTK , 19. říjen 2017 21:26

Mezi zákazníky firmy specializující se na lokalizaci a testování softwaru patří např. Microsoft, IBM...

Více 0 komentářů