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

artificial-intelligence graph-theory dijkstra a-star
Sean picture Sean · Sep 18, 2008 · Viewed 32.7k times · Source

I've read in one of my AI books that popular algorithms (A-Star, Dijkstra) for path-finding in simulation or games is 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 become quite large? Or is that just the way to do it?

Answer

RossFabricant picture RossFabricant · Apr 12, 2009

A good heuristic for A-Star with the 15 puzzle is the number of squares that are in the wrong location. Because you need at least 1 move per square that is out of place, the number of squares out of place is guaranteed to be less than or equal to the number of moves required to solve the puzzle, making it an appropriate heuristic for A-Star.

Related questions

Completeness of depth-first search

I quote from Artificial Intelligence: A Modern Approach: The properties of depth-first search depend strongly on whether the graph-search or tree-search version is used. The graph-search version, which avoids repeated states and redundant paths, is complete in finite state spaces …

Read More
What is the optimal algorithm for the game 2048?

I have recently stumbled upon the game 2048. You merge similar tiles by moving them in any of the four directions to make "bigger" tiles. After each move, a new tile appears at random empty position with a value of either 2 …

Read More
Epoch vs Iteration when training neural networks

What is the difference between epoch and iteration when training a multi-layer perceptron?

Read More