Matematik z Harvardu vyřešil letitý kombinatorický problém šachových královen

08.02.2022 - Stanislav Mihulka

Šachovou hádanku známou jako „problém osmi královen“ se podařilo vyřešit relativně rychle. Její rozšířené zadání pro n královen čekalo na své vyřešení dlouhých 150 let


Reklama

Problém osmi dam je šachová nebo spíše kombinatorická úloha s velmi jednoduchým zadáním. Úkolem je rozmístit osm dam na šachovnici tak, aby se navzájem neohrožovaly. Tento problém poprvé zveřejnil Max Bezzl v roce 1848. Trvalo jen dva roky, než Frank Nauck správně vypočítal počet řešení – osm královen lze na klasické šachovnici rozmístit v celkem 92 rozestaveních, aniž by se mezi sebou ohrožovaly. 

Vedle řešení původního zadání přišel Frank Nauck s novou výzvou zobecněnou jako „n dam na n rozměrné šachovnici“. Toto zadání se ukázalo jako mnohem tvrdší oříšek. Americký institut Clay Mathematics Institute dokonce v roce 2017 nabídl rovný milion dolarů tomu, kdo dokáže napsat algoritmus pro rychlé řešení „problému osmi královen“, nebo dokáže, že je problém neřešitelný. Nauckova výzva zůstávala bez řešení až do loňského roku. Téměř úplným pokořitelem problému n dam se nakonec stal matematik Michael Simkin z centra  Center of Mathematical Sciences and Applications na americkém Harvardu.

Řešení pro n dam

Simkin spočítal, že pro n dam na n rozměrné šachovnici existuje zhruba (0,143 × n) ⁿ řešení. Tento výsledek není dokonale přesnou odpovědí, ale přibližuje nás k ní, jak to jen se současnou úrovní vědomostí a matematických nástrojů dokážeme. Pro matematiky je to přijatelné řešení problému.

TIP: Kolik je v jedné šachové partii možných tahů? Více než atomů v pozorovatelném vesmíru!

Pro představu, pokud bychom měli gigantickou šachovnici s milionem políček na každé ze stran, na kterou bychom měli umístit milion královen, nejprve bychom toto číslo vynásobili 0,143, čímž dostaneme 143 000. Takové číslo je ještě víceméně představitelné. V druhém kroku ale následuje umocnění čísla 143 000 na 1 milion, jehož výsledkem je monumentální cifra s 5 miliony číslic.

Reklama

Další články v sekci

Reklama

Reklama

Aktuální články

Kopcovitá krajina Bílých Karpat státní kontrole dlouho unikala. Náročný terén úředníky od návštěv odrazoval. (foto: Shutterstock)

Zajímavosti

Jediný zachovaný kus německého 128mm samohybného kanonu s přezdívkou „Sturer Emil“ lze zhlédnout v muzeu v ruské Kubince. (foto: Wikimedia Commons, Alan WilsonCC BY-SA 2.0)

Válka

Kmen Bójů neobýval pouze střední Evropu. Mnohem silnější větev žila v severní Itálii, takzvané Předalpské Galii, kde bojovali s Římany, a dokonce je několikrát porazili.(ilustrace: © Martina Nacházelová - se souhlasem k publikování)

Historie

Podle odborníků z NASA je nejzajímavějším cílem pro vybudování měsíční základny oblast Shackletonova a de Gerlacheova kráteru u jižního pólu. (ilustrace: NASA/Advanced Concepts LaboratoryCC0)

Vesmír

Lesní požár na konci permu

Věda

Karikatura zachycující cara Mikuláše II. a Theodora Roosevelta, který apeluje ve věci krutého zacházení s ruskými Židy. (ilustrace: Wikimedia Commons, Emil Flohri, CC0)

Historie

Nové časopisy Extra Publishing

RSSInzerceO serveru (Redakce)Partnerské weby
© Extra Publishing, s. r. o. 2007–2011. ISSN 1804-9907