• 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
Home Články

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

Germanen jako cesta k energeticky úsporné elektronice?
Články

Germanen jako cesta k energeticky úsporné elektronice?

1. 6. 2023
Zprávičky

Neuralink vyvíjející mozkové čipy může zahájit testování na lidech

28. 5. 2023
Umělá inteligence: Nástroje vs. platforma, věda vs. kreativita
Články

Se společností AddAI o AI a chatbotech

23. 5. 2023
Terahertzové vlny si mohou rozumět s těmi spinovými
Články

Terahertzové vlny si mohou rozumět s těmi spinovými

12. 5. 2023

Zprávičky

Amazon jedná o levném či bezplatném volání v USA pro své předplatilete

ČTK
2. 6. 2023

Americká společnost Amazon jedná s telekomunikačními firmami o levném či bezplatném volání ve Spojených

Robot v pražském centru SAP Services ročně naplánuje desítky tisíc pohovorů

Letectvo USA odmítlo tvrzení, že v simulaci dron řízený AI zabil lidského pilota

ČTK
2. 6. 2023

Americký testovací pilot v květnu na vojenské konferenci pro letectví a vesmír řekl, že

Apple představil levný iPhone SE pro sítě 5G

Největší dodavatel Applu začne od dubna 2024 vyrábět iPhony v indické Karnátace

ČTK
2. 6. 2023

Největší dodavatel Applu začne od dubna 2024 vyrábět telefony iPhone v jihoindickém státě Karnátaka.

FSB tvrdí, že Apple spolupracuje s tajnými službami USA

ČTK
1. 6. 2023

Ruská tajná služba FSB tvrdí, že odhalila operaci americké rozvědky, která podle ní využila

CZ.NIC začal zveřejňovat seznam zablokovaných domén

Avast Threat Labs: hackeři útočí na fotbalové fanoušky přes bezplatné streamy zápasů

Pavel Houser
1. 6. 2023

Fanoušci, kteří se chystají 10. června sledovat finále Ligy mistrů UEFA, by si měli

Telly převede své internetové zákazníky pod Nordic Telecom

ČTK
31. 5. 2023

Televizní operátor Telly převede od srpna všechny své uživatele připojení k internetu do sítě

EU a USA usilují o zavedení dobrovolných pravidel pro umělou inteligenci (aktualizováno)

ČTK
31. 5. 2023

Evropská unie a Spojené státy usilují o zavedení dobrovolného souboru pravidel pro odvětví umělé

Tržní hodnota výrobce čipů Nvidia pokořila hranici bilionu dolarů

ČTK
30. 5. 2023

Americká společnost Nvidia se dnes stala prvním výrobcem čipů, jehož tržní hodnota překonala hranici

Tiskové zprávy

Mobilní bankovnictví a platby QR kódem získávají na popularitě

Vědci v ČR získali nejpokročilejší systém pro AI a dva nové clustery pro náročné technické výpočty

Rekordní výsledky Salesforce za první čtvrtletí fiskálního roku 2024: tržby i výnosy meziročně vzrostly o 11 %

Mezi finalisty největší ICT studentské soutěže Huawei jsou čím dál častěji ženy

MiR slaví 10. výročí a pokračuje v globálním růstu

Přepínáte v práci mezi aplikacemi? Ročně tak přijdete o měsíc pracovní doby, zjistil Slack

Zpráva dne

Březnový prodej – doživotní licence na Windows 10 za Goodoffer24 € 12 a Office za € 23!

Březnový prodej – doživotní licence na Windows 10 za Goodoffer24 € 12 a Office za € 23!

Redakce
3. 3. 2023

Ať už hledáte levnější cestu jak postavit nový počítač, nebo jen chcete upgradovat stárnoucí...

Komentujeme

Chvála černých skřínek

ChatGPT – pouhé rozhraní a komprese informací, praví autor sci-fi

Pavel Houser
11. 5. 2023

K hromadám diskusí o konverzačním programu ChatGPT snad stojí za to přidat jeden poměrně nezvyklý (a...

Odebírat newsletter

Zásady ochrany osobních údajů.

Zkontrolujte svoji doručenou poštu a potvrďte odběr.

Slovník

Koučování

Tiskové podklady

HSCSD

Nejpopulárnější články

Nejmenší baterie na světě: 2D systém na čipu

Krystaly lithia mohou vylepšit baterie lithium–kov

Pavel Houser
25. 4. 2023

Evropu čeká pokles prodeje serverů

Redakce
4. 5. 2023

Jak nakupovat – nebo prodávat – data

Boom datové analytiky, odborníci ale firmám chybí

itbiz
27. 4. 2023

Dell rozšiřuje IT kapacity směrem na periferii

Dvě třetiny českých organizací se obávají o svou budoucnost

itbiz
30. 4. 2023

Plně flashové datové centrum: Poslední hřebíček do rakve klasických pevných disků

Plně flashové datové centrum: Poslední hřebíček do rakve klasických pevných disků

Patrick Smith
9. 5. 2023

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 Rozhovory Science Security Technologie Telekomunikace Veřejná správa Vývoj a HTML Zpráva dne České IT

Píšeme jinde

RSS ScienceMag RSS

RSS AbcLinuxu RSS

  • Brave 1.52 s vertikálními kartami. Představeno Brave Search API
  • Red Hat nebude spravovat RPM balíčky pro LibreOffice
  • Počítačové hry zdarma: Tell Me Why a Midnight Ghost Hunt

Newsletter

Zásady ochrany osobních údajů.

Zkontrolujte svoji doručenou poštu a potvrďte odběr.

Žá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.