Povede se informatikům vyřešit zdánlivě jednoduchý matematický problém?
Š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í.
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í.
https://www.stoplusjednicka.cz/kdo-naprogramuje-reseni-problemu-dam-dostane-1-milion-dolaru
Jako to je spíš matematická výzva než programátorská… Je to o tom, nalézt matematický vzorec, podle kterého se budou dámy rozestavovat, naprogramovat to je s takovým vzorcem celkem sranda. Proto taky odměnu nabízí matematický institut… 🙂