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


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

DeOldify: Téměř zázračná technologie, která obarvuje 2. světovou válku, nebo vaše fotky z dětství

DeOldify: Téměř zázračná technologie, která obarvuje 2. světovou válku, nebo vaše fotky z dětství

** Neuronová síť DeOldify obarvuje fotky ** Můžete si ji vyzkoušet sami i bez superpočítače ** YouTube je plný obarvených ikonických videí

Jakub Čížek | 21

Jakub Čížek
PythonHistorieProgramování
Nvidia představila grafické karty GeForce RTX 3090, RTX 3080 a RTX 3070. Známe české ceny

Nvidia představila grafické karty GeForce RTX 3090, RTX 3080 a RTX 3070. Známe české ceny

** Nvidia uvedla nové desktopové grafické karty GeForce RTX 3000 ** Jedná se o modely GeForce RTX 3070, 3080 a 3090 ** K výrobě se používá 8nm technologii od Samsungu

Karel Javůrek | 68

Karel Javůrek
Grafické kartyTechnologieNvidia
Velký test televizorů v Computeru: i levnější značky překvapily kvalitou obrazu

Velký test televizorů v Computeru: i levnější značky překvapily kvalitou obrazu

** Jak funguje biometrické zabezpečení ve Windows ** Nejlepší správci hesel ** Létáme v Microsoft Flight Simulator

Časopis Computer | 5

Časopis Computer
Časopis Computer
Zanedlouho vyjde podzimní verze Windows 10. Podívejte se, co je nového
Vladislav Kluska
Fluent DesignAktualizaceWindows 10Operační systémy
AMD začalo nabízet kola. Celoodpružený model je vyloženě ostuda
David Polesný
CyklistikaAMD
TIP: Lidl má nejlevnější duální Qi nabíječku. Stojí jen 399 Kč
Lukáš Václavík
Bezdrátové nabíjení
10 míst na mapách Googlu, která nesmíte vidět. Nahradily je čtverečky

10 míst na mapách Googlu, která nesmíte vidět. Nahradily je čtverečky

** Deset míst, které nesmíte vidět ve webových mapách ** Jsou to letiště, základny i elektrárny ** Nejvíce míst tají Francie

Jakub Čížek | 21

Jakub Čížek
Mapy GoogleMapy