1.

Zadání

2.

Řešení

3.	Heuristická funkce

4.	Další vylepšení

5.	Struktura programu – datové struktury

6.	Struktura programu – predikáty

7.	Test programu

"Řešení

Stavový prostor úlohy obsahuje 9! = 362880 stavů. Teoreticky by tedy bylo možno provést úplné prohledání celého stavového prostoru. Naše řešení však používá algoritmus prohledávání s heuristickým ohodnocením, tzv. algoritmus A*.
Tento algoritmus přednostně otvírá ty cesty k cíli, které mají lepší ohodnocení získané pomocí heuristické funkce g. Toto ohodnocení se sečte s cenou současné cesty f, čímž získáme výslednou hodnotu h. Podle této hodnoty je postup zařazen do prioritní fronty, ze které jsou odebírány stavy s nejnižším ohodnocením.
Algoritmus A* sice nezaručuje, že bude nalezena nejkratší cesta, přesto je navržen tak, aby při „nepříliš chybné“ heuristické funkci „zřídkakdy nalezl příliš špatné řešení“. (Podrobnosti viz [1])
Heuristická funkce
Jako heuristické ohodnocení používá náš algoritmus součet vzdáleností každého kamene od jeho cílové pozice. (V tzv. Manhattanské metrice, kde r = x+y.)
Další vylepšení
Při generování tahů, možných při aktuálním stavu desky, se neuvažuje takový tah, který by byl jen tahem opačným k minulému tahu (tj. pokud poslední tah byl „vlevo“, nikdy se nezkouší tah „vpravo“ jako pokračování).
Jako prostředek dalšího urychlení algoritmu se v každém kroku ořízne fronta otevřených stavů na 16 nejperspektivnějších stavů. Tím se samozřejmě hypoteticky otevírá možnost, že toto omezení spolu s chybnou heuristickou funkcí nedokáže vůbec najít cestu k cíli, praktické výsledky však tuto možnost nepotvrzují.
Ne každou desku hry Lišák je možno legálními tahy dovést do cílového stavu. Přesněji řečeno, graf tahů ve stavovém prostoru má právě dvě komponenty. Program toto testuje, a pokud je daná deska nedohratelná, predikát vyres (viz níže) selže, aniž by došlo k jinak nevyhnutelnému nekonečnému cyklu při hledání neexistujícího řešení."