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, Tisíc let, Nová verze, Puzzle, Šach, Prolomení, Počítačový odborník, Figurka, Kvíz, Dol, Současný superpočítač, Nový výzkum, Vysoká odměna, Sloup, Oříšek, University of St Andrews, Pořádný oříšek, Online transakce, Transakce, Šachovnice, Dolar, Největší skupina, Královna


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

22 užitečných rozšíření pro Chrome: Naučte prohlížeč nové věci

22 užitečných rozšíření pro Chrome: Naučte prohlížeč nové věci

** Prohlížeč Chrome obsahuje širokou škálu funkcí, neumí ale všechno ** Jeho schopnosti můžete rozšířit pomocí rozšíření ** Vybrali jsme pro vás zajímavé a užitečné doplňky

Karel Kilián | 16

Kryptoměnový milionář staví v Nevadě obří utopické město využívající blockchain na vše

Kryptoměnový milionář staví v Nevadě obří utopické město využívající blockchain na vše

** V USA vzniká rozsáhlý projekt postavený na blockchainu ** Milionář staví město, které bude fungovat zcela na blockchainu ** Blockchain bude základem pro vše, například i platby, ověřování identity a podobně

Karel Javůrek | 41

Notebook do 10 000 korun: Co koupit a čemu se raději vyhnout

Notebook do 10 000 korun: Co koupit a čemu se raději vyhnout

** Do deseti tisíc korun lze dnes koupit slušné notebooky ** V nabídce ale převládají zastaralé a pomalé modely ** Poradíme, jak dobře vybrat i s omezeným rozpočtem

David Polesný | 75