• Technologie
  • Byznys
  • Software
  • Hardware
  • Internet
  • Telco
  • Science
  • České IT
  • Události
Žádné výsledky
Zobrazit všechny výsledky
ITBiz.cz
ITBiz.cz
Žádné výsledky
Zobrazit všechny výsledky

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

Pavel Houser
20. 8. 2015
| Články

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.)

Rubriky: Science

Související příspěvky

Z 2D materiálů dokázali poprvé postavit celý počítač
Články

Z 2D materiálů dokázali poprvé postavit celý počítač

10. 7. 2025
Nebojte se hlásit na seniornější pozice, radí IT pracovní portál
Zprávičky

Umělá inteligence z Matfyzu vytváří srozumitelné právní texty

29. 6. 2025
Flexibilní elektronika naráží na polovodiče typu n
Zprávičky

Prezident si v Ostravě prohlédl kvantový počítač, který je jediný v ČR

26. 5. 2025
Flexibilní elektronika naráží na polovodiče typu n
Články

Tellur zvyšuje výkon 2D polovodičů

22. 5. 2025

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *

Souhlasím se Zásadami ochrany osobních údajů .

Zprávičky

Dell 14 a 16 Premium: Nástupce XPS přináší větší výkon a dlouhou výdrž baterie

Dell 14 a 16 Premium: Nástupce XPS přináší větší výkon a dlouhou výdrž baterie

Pavel Houser
14. 7. 2025

Společnost Dell Technologies představila nové vlajkové lodě svého portfolia notebooků, které navazují na sérii

Jaké novinky přináší Arcserve UDP 8.1?

Analýza: Neviditelným gigantem internetového provozu jsou analytické nástroje

Pavel Houser
14. 7. 2025

V roce 2024 se očekávalo, že dojde k zásadnímu narušení digitálního reklamního průmyslu. Google plánoval zavedení

Europoslanci chtějí omezit příliv levného zboží z e-shopů mimo EU

ČTK
14. 7. 2025

Europoslanci by chtěli omezit rostoucí příliv nekvalitního a potenciálně nebezpečného levného zboží z internetových

Před 30 lety dostaly „empétrojky“ svůj populární název

ČTK
14. 7. 2025

Pro řadu lidí je zkratka mp3 synonymem pro jakoukoliv hudbu uloženou v počítači nebo

SpaceX investuje dvě miliardy USD do Muskovy firmy zaměřené na AI

ČTK
13. 7. 2025

Společnost SpaceX podnikatele Elona Muska investuje dvě miliardy dolarů (42 miliard Kč) do jeho

750 zaměstnanců ČSOB se díky Atosu zvládlo rychle přesunout do domácích kanceláří

Google investuje 2,4 miliardy dolarů do technologie AI od start-upu Windsurf

ČTK
12. 7. 2025

Společnost Google ze skupiny Alphabet zaplatí asi 2,4 miliardy USD (50,64 miliardy Kč) za

Muskova xAI chce další peníze od investorů při ohodnocení na 200 miliard dolarů

ČTK
12. 7. 2025

Americká společnost xAI miliardáře Elona Muska plánuje vybrat peníze od investorů v novém kole

Kryptoměny a jejich ekonomika

Bitcoin pokračuje v růstu na další rekordy, překonal hranici 118 000 dolarů

ČTK
11. 7. 2025

Cena bitcoinu dnes pokračuje v prudkém růstu. Kolem 8:30 SELČ se vyšplhala na další

Tiskové zprávy

Společnost Cato Networks jmenována lídrem v magickém kvadrantu 2025 Gartner Magic Quadrant pro platformy SASE

Společnost QNAP představuje myQNAPcloud One Beta

Acer slaví několikanásobné ocenění cenou Red Dot Product Design Awards 2025

Acer for Business EMEA překonává růst trhu

Nejnovější modely Acer Chromebook Plus nyní s 12měsíčním balíčkem Google AI Pro včetně služby NotebookLM zdarma

ANECT mění vedení společnosti a posiluje management

Zpráva dne

Květen je měsícem růstu, můžete růst s Windows 11 jen za €20.00!

Květen je měsícem růstu, můžete růst s Windows 11 jen za €20.00!

Redakce
15. 5. 2025

Kupte Windows 11 CDkey od Goodoffer24.com a můžete růst s tímto OS jak při...

Komentujeme

Chvála černých skřínek

Malé modely AI mají být velkým trendem

Pavel Houser
3. 1. 2025

V záplavě prognóz technologického vývoje (nejen) v roce 2025 zde prozatím trochu zapadlo jedno téma, které...

Slovník

Internal affair supervisor

Kurz nabídky

Flash mob

Nejpopulárnější články

Žádný obsah není dostupný

Kategorie

  • Články
  • Komentujeme
  • Slovník
  • Tiskové zprávy
  • Zprávičky

Portál ITbiz.cz přináší informace z IT a byznysu již od roku 2006. Provozuje jej internetové vydavatelství Nitemedia. Hosting zajišťuje společnost Greenhousing.cz. Mezi další naše projekty patří například ABClinuxu.cz a Sciencemag.cz. Na stránce Redakce naleznete informace o redakci a možnostech inzerce.

Rubriky

Akce a události Byznys Cloud Ekomerce Hardware Internet Operační systémy Podnikový software Právo Science Security Technologie Telekomunikace Veřejná správa Vývoj a HTML Zpráva dne České IT
Žádné výsledky
Zobrazit všechny výsledky
  • Technologie
  • Byznys
  • Software
  • Hardware
  • Internet
  • Telco
  • Science
  • České IT
  • Události

© 2019 Vydává Nitemedia s.r.o. Hosting zajišťuje Greenhousing.cz.

Tento web používá cookies. Pokračováním dáváte souhlas s jejich používáním. Více na itbiz.cz/soukromi.