Chcete 1 milion dolarů? Stačí vyřešit pekelně těžký šachový kvíz

Chcete 1 milion dolarů? Stačí vyřešit pekelně těžký šachový kvíz

Clay Mathematics Institute nabízí 1 milion USD každému, kdo si dokáže poradit s novou verzí šachového kvízu zvaného Queen's Puzzle. Ale pozor – řešení je prý po matematické stránce tak složité, že jeho nalezení může trvat tisíce let!

Oč jde? Původní Queen's Puzzle se objevilo už v roce 1848 a jeho zadání bylo v zásadě jednoduché – rozmístit 8 královen na standardní 8 × 8 šachovnici tak, aby se žádné dvě z nich přímo neohrožovaly. Háček spočívá v tom, že královna se coby nejsilnější figurka může pohybovat hned v osmi směrech. I tak ale existuje cca 92 různých řešení.

Oproti tomu n-Queens Completion Problem zahrnuje mnohem větší šachovnici i počet královen. Je-li n (počet řádků, sloupců a královen) rovno například tisíci, vzhledem k počtu možných kombinací jde o pořádný oříšek i pro současné superpočítače. A aby to bylo ještě náročnější, v tomto případě nezačínáte s „čistým stolem“ – některá pole jsou již obsazená.

„Nový výzkum se zabývá n-Queens Completion Problem, kde je nejen větší deska, ale některé královny už byly rozmístěny,“ vysvětluje počítačový odborník Ian Gent z University of St Andrews. „Pokud jsou tedy některé královny na desce n × n už umístěny, dokážete najít řešení n-Queens puzzle, aniž byste některou z nich přesunuli?“

Kdyby se někomu podařilo napsat algoritmus, který by to efektivně zvládal (pro jakoukoliv hodnotu n), měl by v rukou klíč k řešení veškerých dalších podobných problémů s vysokými proměnnými.

„Jedná se o triviální výzvy, jako je vytvoření největší skupiny vašich facebookových přátel, kteří se navzájem neznají, nebo velmi důležité, jako je prolomení kódů, které zabezpečují veškeré online transakce,“ uvedl Gent. Už chápete, proč tak vysoká odměna?

Zdroj: University of St Andrews

Diskuze (20) Další článek: Apple má zájem o divizi Toshiby pro výrobu čipů, chce přebít Western Digital

Témata článku: Výzkum, Programování, Superpočítače, Dol, Sloup, Nová verze, Šachovnice, Počítačový odborník, Řešení, Kvíz, Online transakce, Královna, Transakce, University of St Andrews, Nový výzkum, Prolomení, Nalezení, Vysoká odměna, Oříšek, Figurka, Šach, Současný superpočítač, Možná kombinace, Tisíc let, Queens


Určitě si přečtěte

AR není ani po letech žádný trhák. Teď to zkusí Hybri, který svleče vaše kamarádky

AR není ani po letech žádný trhák. Teď to zkusí Hybri, který svleče vaše kamarádky

** Rozšířené realitě i po letech chybí praktické využití ** Selhaly mobilní aplikace i AR brýle ** Floridské studio to proto zkusí přes bizarní erotiku Hybri

Jakub Čížek | 20

Z rozmazané šmouhy krásná fotka. Takhle kouzlí nová umělá inteligence MyHeritage

Z rozmazané šmouhy krásná fotka. Takhle kouzlí nová umělá inteligence MyHeritage

** MyHeritage slibuje nejlepší neuronovou síť pro vylepšování fotek ** Funguje tím líp, čím horší fotku upravuje ** Otestovali jsme desítky různých snímků

Marek Lutonský, Lukáš Václavík | 39

Nejlepší programy z roku 2000: Podívejte se, bez čeho jste tehdy vůbec nemohli fungovat!

Nejlepší programy z roku 2000: Podívejte se, bez čeho jste tehdy vůbec nemohli fungovat!

** Dnes už skoro všechno uděláte ve webovém prohlížeči a na mobilu ** Před dvaceti lety to ale bylo jiné ** Zavzpomínejte na legendy, které jste pravděpodobně také používali

Jakub Čížek | 126