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

Chatbot mluví za mrtvého – od nápadu k realizaci

Pavel Houser , 30. listopad 2016 13:00
Pavel Houser

Na webu The Verge popsala Casey Newton příběh dvou přátel (Eugenia Kuyda a Roman Mazurenko). Peripet...

Více





Kalendář

RSS 

Zprávičky

Za vzněcováním smartphonu iPhone 6 jsou vnější vlivy, tvrdí Apple

ČTK , 08. prosinec 2016 11:30

Firma Apple odmítla podezření čínských uživatelů svého chytrého telefonu iPhone 6, že za problémy s ...

Více 0 komentářů

Verizon prodá firmě Equinix datová centra za 3,6 miliardy USD

ČTK , 08. prosinec 2016 10:00

Největší americký mobilní operátor Verizon Communications prodá specializované společnosti Equinix 2...

Více 0 komentářů

Tchajwanský Foxconn jedná o rozšíření svých aktivit v USA

ČTK , 07. prosinec 2016 15:00

Tchajwanská společnost Foxconn jedná o rozšíření svých aktivit ve Spojených státech. Oznámila to dne...

Více 0 komentářů

Starší zprávičky

Nejvyšší soud USA se postavil na stranu Samsungu proti Applu

ČTK , 07. prosinec 2016 12:30

Americký nejvyšší soud se v mnohaletém patentovém sporu mezi výrobci chytrých telefonů Apple a Samsu...

Více 0 komentářů

Evropská komise Microsoftu schválila převzetí sítě LinkedIn

ČTK , 07. prosinec 2016 10:30

Evropská komise schválila americké softwarové společnosti Microsoft záměr koupit za 26 miliard dolar...

Více 0 komentářů

Porozumění větám, konkurence pro Turingův test

Pavel Houser , 06. prosinec 2016 18:00

Konverzační roboti mají stále problémy pochopit věty, kde smysl nelze vyvodit ze samotné gramatické ...

Více 0 komentářů

Americká GoDaddy koupí evropský webhosting Host Europe

ČTK , 06. prosinec 2016 16:00

Americký registrátor internetových domén GoDaddy, který je ve svém oboru největší na světě, se dohod...

Více 0 komentářů