• 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

Matematika rychlostí světla: Optické počítání může být i analogové
Články

Matematika rychlostí světla: Optické počítání může být i analogové

27. 3. 2023
Zprávičky

Lidé budou mít jednou mobilní telefon integrovaný do těla, myslí si vynálezce

2. 3. 2023
Podařilo připravit husté křemíkové nanodrátky pro aplikace s vysokými frekvencemi
Články

Maxwellův démon resetuje qubity kvantového počítače

27. 2. 2023
Atos představil superpočítač BullSequana XH3000
Zprávičky

Atos postaví další superpočítač pro vědce

21. 2. 2023

Zprávičky

Padla další rekordní pokuta za porušení GDPR

Digitalizace veřejné správy pod jednou střechou, DIA zahajuje svou činnost

Pavel Houser
30. 3. 2023

Od 1. dubna 2023 začíná fungovat Digitální a informační agentura (DIA), která bude mít

Vodafone v Německu zruší přes 6 % pracovních míst

ČTK
30. 3. 2023

Telekomunikační společnost Vodafone se v Německu chystá zrušit přes šest procent pracovních míst, a

Musk a další chtějí kvůli vážným rizikům pauzu ve vývoji umělé inteligence

ČTK
29. 3. 2023

Stovky akademiků, expertů a podnikatelů zapojených do vývoje umělé inteligence (AI) včetně miliardáře Elona

Pětice motorů technologických inovací v příští dekádě

Goldman Sachs: Umělá inteligence by mohla nahradit 300 milionů pracovních míst

ČTK
29. 3. 2023

Umělá inteligence by mohla ve světě nahradit člověka na 300 milionech pracovních míst. Vyplývá

Kryptoměny a jejich ekonomika

Americké úřady žalují kryptoměnovou burzu Binance za porušení předpisů

ČTK
28. 3. 2023

Americká Komise pro obchodování s termínovými kontrakty na komodity (CFTC) žaluje největší kryptoměnovou burzu

EK opět odmítla návrh ČTÚ na regulaci velkoobchodního trhu s mobilními daty

ČTK
27. 3. 2023

Evropská komise opět odmítla návrh Českého telekomunikačního úřadu (ČTÚ) na regulaci velkoobchodního trhu s

Intenzita jednotlivých DDoS útoků na české firmy v únoru rostla, nejvíce útoků míří z Ruska

Pavel Houser
27. 3. 2023

Počet DDoS útoků na české firmy v únoru klesl, zvýšila se ale intenzita jednotlivých útoků.

Sophos představil XDR řešení pro synchronizované zabezpečení

Acronis vylepšuje své bezpečnostní řešení o technologii Intel TDT

Pavel Houser
27. 3. 2023

Řada aktuálních hrozeb využívá pouze přístup do paměti. Acronis oznámil vylepšení své bezpečnostní ochrany

Tiskové zprávy

Česko-americký startup MANTA otevírá novou pobočku v Londýně

CETIN: průměrná rychlost dostupného připojení v síti se dostala na 202 Mb/s

Nová modulární roll-to-roll tiskárna Canon Colorado řady M

Česká platforma TENT.com umožňuje platby kryptem kdekoliv

T-Mobile chce chránit zákazníky před podvodnými telefonáty

Premiér Fiala se připojil k otevřenému dopisu předsedů vlád šéfům technologických gigantů

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

Odebírat newsletter

Zásady ochrany osobních údajů.

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

Komentujeme

Chvála černých skřínek

Programování s pomocí umělé inteligence a open source licence

Pavel Houser
15. 3. 2023

S tím, jak se rozšiřuje využití umělé inteligence přímo při tvorbě softwaru, se intenzivněji začínají diskutovat...

Nadcházející akce

  1. Hannover Messe 2023

    17. dubna - 21. dubna

Zobrazit všechny Akce

Slovník

Efektivita

AIBO

Ban

Nejpopulárnější články

OKI na veletrhu EmbaxPrint zaujala potiskem etiket

OKI na veletrhu EmbaxPrint zaujala potiskem etiket

Tomáš Jirásko
1. 3. 2023

Kvalitních IT specialistů je nedostatek a práce na dálku jim může přinést až o 25 % víc peněz

Redakce
3. 3. 2023

Umělá inteligence: Nástroje vs. platforma, věda vs. kreativita

ChatGPT uspěl v testu teorie mysli

Pavel Houser
21. 2. 2023

Mýty kolem digitalizace firmy (1): Digitalizace je jen IT projekt a adopce je ztráta času

Mýty kolem digitalizace firmy (1): Digitalizace je jen IT projekt a adopce je ztráta času

itbiz
2. 3. 2023

Kouzla zbavené? Nepravděpodobné řešení hrozící personální krize ve finančních službách

10 let ABSL: Firmy využívající umělou inteligenci rostou rychleji

Redakce
2. 3. 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 techn Technologie Telekomunikace Veřejná správa Vývoj a HTML Zpráva dne České IT česk

Píšeme jinde

RSS ScienceMag RSS

  • Astronomové zkoumají zrod kupy galaxií v mladém vesmíru
  • Čeští vědci přispěli s mini-družicí GRBAlpha k pozorování nejmohutnější exploze od počátku lidské civilizace
  • Vysokorychlostní kamera ukázala srážku blesku s protibleskem

RSS AbcLinuxu RSS

  • Výsledky hackerské soutěže Pwn2Own Vancouver 2023
  • WordPress 6.2 Dolphy
  • Blender 3.5

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.