Příklad číslo 5

Napište program, který vybere nejlepší tah Lloydovy patnáctky.

Lloydova patnáctka

je hlavolam, považovaný za jednoduchého předchůdce Rubikovy kostky. Jedná se o patnáct stejně velkých čtvercových kamenů, uložených v ploché čtvercové krabičce s kapacitou 4x4 kameny (místům pro jednotlivé kameny budeme dále říkat buňky). Jedna buňka je tedy volná a lze na ni přesunout některý ze sousedních kamenů. Tento přesun je tahem. Kameny jsou očíslovány od jedné do patnácti. Na začátku jsou kameny náhodně promíchány, cílem je pomocí vhodné posloupnosti tahů dosáhnout cílovou pozici:

Vstup

programu je popis zkoumané pozice. Je to šestnáct čísel, udávajících čísla kamenů, ležících v buňkách zleva doprava, shora dolů (tedy nejprve kámen na pozici [1,1], [1,2], [1,3] ... [4,4]). Prázdné místo je reprezentováno číslem 0. Například výše nakreslená cílová pozice by byla zadána posloupností:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0

Výstup

má být buňka (číslo řádku a sloupce) kamene, jehož přesun na volné místo povede k nejlepší pozici.

Pro posouzení pozice použijte následující ohodnocovací funkci: Pro každý kámen se sečte počet sloupců a počet řádků, o které je vzdálen od své cílové buňky. Součet takto vzniklých čísel pro všech patnáct kamenů je výsledkem ohodnocovací funkce pro pozici. Lepší je pochopitelně pozice s nižší hodnotou funkce.