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

Témata článku: Programování, Výzkum, Superpočítače, Nová verze, Královna, Největší skupina, Transakce, Současný superpočítač, Online transakce, Dolar, Počítačový odborník, Puzzle, Řešení, University of St Andrews, Kvíz, Šachovnice, Nový výzkum

19 komentářů

Nejnovější komentáře

  • Pavel Svoboda 8. 9. 2017 17:36:06
    Takže odměna není za to najít řešení, ale vymyslet algoritmus. No kdybych...
  • Nargon 5. 9. 2017 7:34:44
    A co to zkusit zadat umělé inteligenci, jestli najde řešení. Prý je to...
  • Jan Smetana 4. 9. 2017 23:17:00
    Asi bych zacal hledat tady: https://projecteuler.net/problem=534
Určitě si přečtěte

Asteroid se rozpadl a začal se chovat jako kometa

Asteroid se rozpadl a začal se chovat jako kometa

** 288P se nachází v hlavním pásu planetek mezi Marsem a Jupiterem ** Dvě podobně velká tělesa obíhají okolo sebe po velmi protáhlé dráze ** Po přiblížení ke Slunci vykazují kometární aktivitu

Včera | Kubala Petr