Sliding puzzle 4x4

Witam :)
Czy ktoś robił przesuwaną układankę 4x4 i więcej w oparciu o wzorcowe bazy danych ? Znalazłem coś takiego w internecie próbowałem napisać sam ale przy testowaniu 3x3 daje mi trochę inne wyniki niż funkcja manhattan distance. Krótko mówiąc testując wzrocową bazę danych nie otrzymuję optymalnego rozwiązania np. instancja dla układanki 3x3 daje 15 ruchów przy korzystaniu manhattan distance natomiast dla wzorcowej bazy danych 17 ruchów. Czy taka rozbieżność jest ok ?

Link do strony opisującej algorytm. https://algorithmsinsight.wordpress.com/graph-theory-2/implementing-bfs-for-pattern-database

Proszę przedstawić swoją implementację wraz z opisem (komentarze w kodzie), jak ona dokładnie działa. Do tego co najmniej 3 przypadki testowe, czyli pierwotny stan układanki, to co Tobie wychodzi i to, co wg Ciebie powinno wyjść wg bazy wzorcowej.

To wszystko napisz po to, żeby było "czarno na białym", jak działa Twoja implementacja, czym różni się ona od opisanego algorytmu. Wtedy będzie można dyskutować, czy zachowanie Twojej wersji jest prawidłowe i co trzeba zmienić w razie czego.