Un graf de stari
Fiecare configuratie a pieselor este un nod. Doua configuratii sunt vecine daca o mutare legala transforma una in cealalta.
O muchie reprezinta o mutare, nu o distanta in spatiu. Daca fiecare mutare costa 1, drumul minim foloseste cele mai putine mutari.
Rezolvare
1. Alegem configuratia initiala si configuratia-tinta.
2. Generam vecinii unei configuratii prin mutari legale.
3. Aplicam cautare cu cost uniform (echivalenta cu Dijkstra pentru costuri unitare) sau A* cu o euristica admisibila.
4. Reconstituim succesiunea mutarilor.
Ce este surprinzator?
Puzzle-ul 15 are 16!/2 = 10.461.394.944.000 configuratii accesibile dintr-o stare data. De aceea, explorarea tuturor starilor nu este practica; o euristica buna poate reduce enorm cautarea.