Programátorská výzva: Milion dolarů za řešení „problému osmi královen“

04.09.2017 - Stanislav Mihulka

Povede se informatikům vyřešit zdánlivě jednoduchý matematický problém?

<p>Vyřeší někdo Problém dam pro počítače?</p>

Vyřeší někdo Problém dam pro počítače?


Reklama

Šachová úloha, či spíše kombinatorický problém známý jako „problém osmi královen“ je vlastně velmi jednoduchý - cílem je na běžné šachovncici nalézt všechny možné pozice královen tak, aby se navzájem neohrožovaly šachovými tahy.

Když počítače hrají v šach

Zadání s 8 dámami zvládne každý, kdo umí hrát šachy a má dost trpělivosti. Možných řešení této úlohy je celkem 92. Co se ale stane, pokud šachovnci zvětšíme a umístíme na ni větší počet figur? Úlohu lze zobecnit na problém n dam, tedy otázku, jak lze rozmístit n dam na šachovnici o rozměrech n × n tak, aby se vzájemně neohrožovaly. Zmíněná úloha je pro svou názornost využívá při výuce programování.

Počítače řeší tento problém hrubou silou. Prostě zkouší jednu možnost za druhou, dokud nevyčerpají všechna řešení. Podle odborníků ale tento přístup funguje do velikosti šachovnice 1 000 × 1 000 polí. Pak už jsou výpočty tak komplikované, že to ani dnešní počítače nezvládají.

TIP: Důstojná oslava: Číslo pí už známe na dalších 9 bilionů desetinných míst

Americký institut Clay Mathematics Institute proto nabízí 1 milion dolarů (asi 22 milionů Kč) tomu, kdo dokáže napsat algoritmus pro rychlé řešení „problému osmi královen“, nebo dokáže, že to není možné. Nejde o nikterak jednoduché zadání, pokud ale někdo uspěje, mohlo by to podle odborníků změnit samotné základy programování.

Reklama

  • Zdroj textu:

    University of St. Andrews

  • Zdroj fotografií: CC0 Creative Commons



Další články v sekci

Reklama

Reklama

Aktuální články

Dospělá samice skákavky pruhované (Salticus scenicus) z čeledi skákavkovití (Salticidae). (foto: Wikimedia Commons, Kaldari, CC0 1.0)

Věda

Kanadští kulometčíci během bitvy u Vimy, někteří důstojníci je trestali například jen za bláto na kalhotách. (foto: Wikimedia Commons, Library and Archives Canada, CC0)

Válka

Půlmetrový meteorit CNEOS 2014-01-08 je podle vědců nejstarším známým mezihvězdným návštěvníkem. V roce 2017 astronomové zaznamenali průlet objektu 'Oumuamua a o dva roky později průlet mezihvězdné komety 2I/Borisov

Vesmír
Revue
Zajímavosti

Lýdský král Kroisos ukazuje své pohádkové bohatství, autor Gaspar van den Hoecke (kolem 1630) (ilustrace: Wikimedia Commons, Národní muzeum ve Varšavě, CC0)

Historie

Nové časopisy Extra Publishing

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