Algorytm do 8-Puzzle

Witam, mam do zrobienia program, który będzie rozwiązywał łamigłówki typu 8-Puzzle.
Generalnie, wszędzie gdzie czytam o algorytmie do tego i sposobie na rozwiązanie to w pewnym momencie artykuł się kończy, nie wyjaśniając ważnych kwestii. Inne pomoce typu pseudokod z wikipedii też niewiele dają, bo są zupełnie niezrozumiałe.

Nie wiem w jaki sposób mam się kierować w wyborze pola do przesunięcia lub jak się kierować "wycofaniem", gdy okaże się, że droga jednak nie jest dobra (no właśnie, jak stwierdzić, że nie jest dobra?) Weźmy przykład.

Wejście: Cel:
1 4 7 1 4 7
6 5 2 5 8
2 3 8 3 6

A więc, na wejściu możemy ruszyć pustą kratką do góry, w lewo oraz w dół.

1. Którą stronę wybrać? Czy po prostu każdą po kolei?
2. Wzięliśmy jakąś losową drogę typu: DÓŁ LEWO LEWO GÓRA PRAWO DÓŁ LEWO GÓRA GÓRA... i tak można w nieskończoność. Kiedy skończyć?

o_O
http://www.brian-borowski.com/software/puzzle/
http://stackoverflow.com/questions/1395513/what-can-be-the-efficient-approach-to-solve-the-8-puzzle-problem
https://www.cs.princeton.edu/courses/archive/spr10/cos226/assignments/8puzzle.html
każdy z tych linków zawiera kompletny opis algorytmu. I nie, nie ma on nic wspólnego z żadną losową drogą...

Gdyby na zajęciach z Algorytmów mówili po co są te całe grafy... Ale nie! MACIE SIĘ NAUCZYĆ GRAFÓW I KONIEC. "Dlaczego mam rozumieć coś, o zastosowaniu czego nie wiem kompletnie nic?", pomyślałem. Pamiętam, że prawie nie zaliczyłem przedmiotu za ściąganie...