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, Figurka, Počítačový odborník, Vysoká odměna, Současný superpočítač, Tisíc let, Queens, Puzzle, Řešení, Šach, Nalezení, Prolomení, Nová verze, Dol, Online transakce, Transakce, Kvíz, Sloup, Největší skupina, Oříšek, Možná kombinace, Královna, Pořádný oříšek


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

Už desítky let se pokoušíme odposlouchávat mozek. Rusům se podařil kousek, ze kterého vám spadne brada

Už desítky let se pokoušíme odposlouchávat mozek. Rusům se podařil kousek, ze kterého vám spadne brada

** K odposlechu mozků používáme EEG ** To má ale žalostné informační rozlišení ** Rusům pomohla počítačová neuronová síť

Jakub Čížek | 28

Starý smartphone nemusí skončit v koši. 10 způsobů, jak ho ještě můžete využít

Starý smartphone nemusí skončit v koši. 10 způsobů, jak ho ještě můžete využít

** Co dělat s vysloužilým chytrým telefonem? Neházejte ho do koše! ** Našli jsme pro vás deset možností, jak ho prakticky využít ** I stará zařízení tak mohou být užitečná

Karel Kilián | 47

Nejlepší notebooky do 10 000 korun: Co koupit a čemu se raději vyhnout

Nejlepší notebooky 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 i tak převládají zastaralé a pomalé modely ** Poradíme, jak dobře vybrat i s omezeným rozpočtem

David Polesný | 99