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


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

Temný režim a spousta vychytávek. Vyzkoušeli jsme nový macOS 10.14 Mojave

Temný režim a spousta vychytávek. Vyzkoušeli jsme nový macOS 10.14 Mojave

** Vyzkoušeli jsme veřejnou betu macOS 10.14 Mojave ** Hlavní novinkou je temný režim a velký důraz na soukromí ** Jako první beta je systém překvapivě rychlý a dobře použitelný.

Martin Miksa | 35

USB-C už mělo být všude, ale není. Tak kde to vázne?

USB-C už mělo být všude, ale není. Tak kde to vázne?

** Konektor USB-C byl představen už před čtyřmi roky ** Praktické univesrzální rozhraní však stále není rozšířeno ** Výrobcům hardwaru se do změny moc nechce

David Polesný, Vladislav Kluska | 87

17 tipů, jak se nenechat hacknout

17 tipů, jak se nenechat hacknout

** Přehled nejdůležitějších věcí, které je nutné dodržovat pro digitální bezpečnosti ** Hlavní je používat mozek ** Chraňte soukromé informace

Karel Javůrek | 25

Vyzkoušeli jsme eObčanku a přihlásili se s ní na weby úřadů. Vážně to funguje!

Vyzkoušeli jsme eObčanku a přihlásili se s ní na weby úřadů. Vážně to funguje!

** Máme eObčanku, máme čtečku, vyzkoušeli jsme přihlášení na weby úřadů. ** Objevily se drobné problémy, podařilo se nám je vyřešit. ** Používání eObčanky pro online identifikaci je velmi pohodlné.

Marek Lutonský | 34

Nová zbraň Microsoftu proti iPadu: Levný tablet Surface Go bude stát jen deset tisíc

Nová zbraň Microsoftu proti iPadu: Levný tablet Surface Go bude stát jen deset tisíc

** Microsoft představil nový tablet Surface Go ** Nový model zaujme nízkou cenou, ale schopnostmi zařízení Surface ** Microsoft nepoužil čip ARM, ale klasický procesor od Intelu 

Karel Javůrek | 117

Limitovaná nabídka: Windows 10 Professional za pouhých $11.90

Limitovaná nabídka: Windows 10 Professional za pouhých $11.90

Goodoffer24.com Je nový eshop s licencemi a softwarovými klíči, který nabízí nejlepší ceny a rychlé dodání produktu na e-mail. Kromě licencí pro Windows 10 Pro, nabízí web také řadu špičkových produktů, jako je Xbox Live Gold membership nebo oblíbený titul – PLAYERUNKNOWN’S BATTLEGROUNDS.

Intel vs. AMD: souboj vícejádrových procesorů začal. AMD zesměšňuje Intel neuvěřitelně nízkou cenou

Intel vs. AMD: souboj vícejádrových procesorů začal. AMD zesměšňuje Intel neuvěřitelně nízkou cenou

** AMD představilo nové levné procesory až s 32jádry ** AMD útočí na serverový i domácí trh Intelu ** Intel nemá konkurenceschopnou nabídku

Karel Javůrek | 84

Portál občana už funguje. Na státní web vypadá až překvapivě použitelně

Portál občana už funguje. Na státní web vypadá až překvapivě použitelně

** Portál občana už funguje, vyřídíte na něm první požadavky ** Funkce se budou postupně rozšiřovat ** Web je docela moderní a přehledný

David Polesný | 66


Jízdní řády Bileto
Aktuální číslo časopisu Computer

Jak mobily určují svoji polohu?

Velký test notebooků pro studenty

Nejlepší reproduktory na párty

Služby a aplikace pro výuku angličtiny