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



Herní dělo Asus ROG Phone 5s Pro uhrane výkonem i dvěma barevnými displeji

Herní dělo Asus ROG Phone 5s Pro uhrane výkonem i dvěma barevnými displeji

** Asus ROG Phone 5S pro je opět to nejlepší pro mobilní hráče ** Má dva barevné displeje a ještě vyšší výkon ** Za skvělý zážitek si ale připlatíte

Martin Miksa
ROGHerní mobilyVideo
Na povrchu Měsíce je tolik kyslíku, že by stačil pro lidstvo na 100 tisíc let

Na povrchu Měsíce je tolik kyslíku, že by stačil pro lidstvo na 100 tisíc let

** Lidstvo se připravuje na kolonizaci Měsíce ** Jednou ze základních surovin, bez nichž se na naší přirozené družici neobejdeme, je nepochybně kyslík ** Kde ho vzít?

Stanislav Mihulka
KolonizaceMěsícO2
Jeden z nejpodivnějších objektů ve Sluneční soustavě odpálil další explozi

Jeden z nejpodivnějších objektů ve Sluneční soustavě odpálil další explozi

** Kometa 29P/Schwassmann–Wachmann je pozoruhodná tím, že víceméně pravidelně vybuchuje ** A letos se vyloženě předvádí ** V srpnu odpálila pořádnou erupci, v září doslova supererupci a 24. října následovala další velice silná exploze

Stanislav Mihulka
AstronomieKomety
Korpusový vyhledávač Kontext Alpha je tajná zbraň každého milovníka češtiny

Korpusový vyhledávač Kontext Alpha je tajná zbraň každého milovníka češtiny

** Český národní korpus analyzuje tisíce textů ze všech oblastí života ** Vyhledávač Kontext v něm umí dokonale vyhledávat ** Je to skvělý nástroj pro milovníky češtiny a zbraň grammar nazis

Jakub Čížek
ČeskoVyhledávače
Lék proti depresi za stokorunu snižuje riziko těžkého průběhu i úmrtí na onemocnění covid-19

Lék proti depresi za stokorunu snižuje riziko těžkého průběhu i úmrtí na onemocnění covid-19

** Klinická studie zkoumala vliv antidepresiva fluvoxamin na covid-19 ** Počet úmrtí souvisejících s covidem-19 klesl zhruba o 90 % ** Potřeba intenzivní lékařské péče se snížila zhruba o 65 %

Karel Kilián
COVID-19LékyDepreseMedicína