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?

Šachová královna -<p>Vyřeší někdo Problém dam pro počítače?</p>
Šachová královna -

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, 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í.

  • Zdroj textu:

    University of St. Andrews

  • Zdroj fotografií: CC0 Creative Commons

Reklama

Další články v sekci

Reklama

Reklama

Aktuální články

Mezi hlavní úkoly nindžů patřilo pronikat v přestrojení za nepřátelské linie a vynášet informace či zabíjet.

Zajímavosti

Dospělá kareta obecná (Caretta caretta) dorůstá bezmála jednoho metru a běžně váží více než sto kilogramů.

Příroda

Mládí prožila v radovánkách a nicnedělání

Historie

Povrch měsíce Europa

Vesmír

Tradice velí, že muž zajišťuje financování domácnosti. Jinak to pro muže bývá stresující.

Věda
Věda

Nové časopisy Extra Publishing

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