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: Programování, Výzkum, Superpočítače, Nalezení, Sloup, University of St Andrews, Nová verze, Šach, Puzzle, Kvíz, Tisíc let, Možná kombinace, Počítačový odborník, Oříšek, Online transakce, Největší skupina, Šachovnice, Transakce, Královna, Řešení, Nový výzkum, Dolar, Pořádný oříšek, Prolomení, Současný superpočítač


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

Velká podzimní aktualizace: Co nového teď najdete ve Windows 10

Velká podzimní aktualizace: Co nového teď najdete ve Windows 10

** Microsoft se opět snaží spojit telefony a počítače. ** Místo velkých novinek se zaměřil spíše na drobná vylepšení. ** Vyhledávání je konečně použitelné a hledá téměř všude.

Vladislav Kluska | 78

Kde se bere elektřina v zásuvce? Poznejte 10 tajemství venkovních stožárů s dráty

Kde se bere elektřina v zásuvce? Poznejte 10 tajemství venkovních stožárů s dráty

Elektřina se vyrábí v elektrárnách, ale do zásuvek v našich domovech to pak má ještě hodně daleko. Dnes se na tuhle dlouhou cestu podíváme.

David Polesný | 82

Američtí mariňáci si tisknou kasárna z betonu na 3D tiskárně

Američtí mariňáci si tisknou kasárna z betonu na 3D tiskárně

** Americká námořní pěchota nedávno představila 3D tištěná kasárna pro vojáky ** Ty jim tiskne velká 3D tiskárna na beton ** Výsledkem je solidní obytný prostor, který je slušně chráněný před nepřátelskou palbou

Stanislav Mihulka | 18

Čtyřicet procent je moc. Spalovací motory nedokážou splnit požadavek EU na snížení emisí

Čtyřicet procent je moc. Spalovací motory nedokážou splnit požadavek EU na snížení emisí

** EP nařídil automobilkám snížit o 40 % emise CO2 ** EU chce zvýšit podíl elektromobilů ** Výrobci hrozí ztrátou pracovních míst

Karel Kilián | 254


Aktuální číslo časopisu Computer

Jak vytvořit a spravovat vlastní web

Velký test herních klávesnic a DVB-T2 tunerů

Vše o formátu RAW

Vybíráme nejlepší základní desku