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

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