How do you solve the 15-puzzle with A-Star or Dijkstra's Algorithm?

Question

I've read in one of my AI books that popular algorithms (A-Star, Dijkstra) for path-finding in simulation or games are also used to solve the well-known "15-puzzle".

Can anyone give me some pointers on how I would reduce the 15-puzzle to a graph of nodes and edges so that I could apply one of these algorithms?

If I were to treat each node in the graph as a game state then wouldn't that tree becomes quite large? Or is that just the way to do it?

Answer 1

Dijkstra's algorithm allows us to find the shortest path from one vertex in a graph to all other vertices in the graph. It is a great algorithm for finding the shortest path in an explicit graph (that is, a graph that is defined using an adjacency list or an adjacency matrix). However, if the graph is implicit (we don't have the actual graph, just rules for how it can be created), then Dijkstra's algorithm can be problematic.

In my opinion, you can use either of the two approaches, as it depends on the problem.

You can refer the following link which solves the fifteen puzzle in Java using A* and Dijkstra's algorithm:

https://gist.github.com/leopd/5992493

Interested in learning Artificial Intelligence? Learn more from this Artificial Intelligence Online Course!