Algorithm for solving 8 puzzle with A* works in a way that we have priority queue and we repeatedly remove minimum priority boards and add its neighbours to queue. Now I don't understand what happens when some old neighbour still in queue becomes one with least priority and it gets chosen as next board. Problem is that nothing guarantes that it is legal move to go from current board to the that old neightbour. For priority function is used manhattan distance + moves since begining.
I somehow did succeeded in implementing valid solver but I don't know why above mentioned case never happens.