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, Nová verze, Oříšek, Dolar, Nový výzkum, Figurka, Transakce, Tisíc let, University of St Andrews, Počítačový odborník, Královna, Současný superpočítač, Kvíz, Queens, SAC, Šach, Možná kombinace, Dol, Nalezení, Řešení, Online transakce, Prolomení, Šachovnice



Jak fotí Huawei Mate 50 Pro. Ani jeden z nejlepších fotomobilů se nevyhnul pár přešlapům

Jak fotí Huawei Mate 50 Pro. Ani jeden z nejlepších fotomobilů se nevyhnul pár přešlapům

** Huawei Mate 50 Pro je podle Dxomarku nejlepší současný fotomobil ** Za slunného dne vykouzlí nádherné ostré snímky ** Trpí na šum, špatné vyvážení bílé nebo odlesky v protisvětle

Jan Pánek
Jak fotíFotomobilyFocení mobilem
Zadejte tajný kód a můžete hrát. V telefonech s Androidem je ukrytá fotbalová hra Mini Cup

Zadejte tajný kód a můžete hrát. V telefonech s Androidem je ukrytá fotbalová hra Mini Cup

** Google si občas ve vyhledávači připraví skryté animace či hry ** Tentokrát se týká fotbalového mistrovství světa ** Stačí do vyhledávače v mobilu zadat dvojici slov...

Martin Chroust
VyhledávačSmartphonyMobilní hry
Facebook má nejspíš vaše telefonní číslo, i když jste mu ho nikdy nedali. Tímto tajným nástrojem ho můžete smazat

Facebook má nejspíš vaše telefonní číslo, i když jste mu ho nikdy nedali. Tímto tajným nástrojem ho můžete smazat

**Meta poskytuje nástroj na vymazání telefonních čísel a e-mailových adres z Facebooku a Instagramu **V minulosti Mark Zuckebrg popřel, že by Facebook vytvářel stínové profily **Metě teď můžete sebrat klíčové iddentifikátory, pořád o vás ale nejspíš ví mnoho dalšího

Petr Urban
MetaSledováníSociální sítě
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