I am looking for an algorithm to solve a "sliding puzzle", the kind of puzzle where you have an image broken into 16 pieces in a 4x4 frame

Question

I am looking for an algorithm to solve a "sliding puzzle", the kind of puzzle where you have an image broken into 16 pieces in a 4x4 frame, that you try to reassemble for a scrambled starting position. This particular puzzle has a restriction, the rows move only to the right (and wrap around), the whole row at once and the columns move only up (and wrap around), the whole column at once, both in one-tile steps. Is the math too complex? Anyone has experience with this kind of problem?

Answer 1

This link will provide you the answer. They talk about the different distance functions used by the heuristic. A* is simpler to find open source implementations of.

Answer 2

as for pretty much any problem, one "easy/simple" method to solve such a problem is to represent puzzle states as a graph, and use a graph search / path finding algorithm (DFS,BFS,Dijkstra,A*,etc.). Maybe there is some genius special algorithm that fits this problem better, but you would probably need quite a lot of insight to get better than A* / bidirectional dijkstra.