views:

3848

answers:

7

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?

+1  A: 

Just use the game tree. Remember that a tree is a special form of graph.

In your case the leaves of each node will be the game position after you make one of the moves that is available at the current node.

David Locke
+5  A: 

A quick Google search turns up a couple papers that cover this in some detail: one on Parallel Combinatorial Search, and one on External-Memory Graph Search

General rule of thumb when it comes to algorithmic problems: someone has likely done it before you, and published their findings.

Michael Dorfman
A: 

Also. be mindful that with the A-Star algorithm, at least, you will need to figure out a admissible heuristic to determine whether a possible next step is closer to the finished route than another step.

Hans Sjunnesson
+2  A: 

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.

RossFabricant
I don't think your proposed metric is well suited to the problem. Intuitively it would be quite vulnerable to situations with a few pieces on the wrong side of the board. You'd probably do better with the sum of the distances from their final position.
wowest
You're right, that's better, but mine will also work.
RossFabricant
A: 

Here you go http://www.heyes-jones.com/astar.html

+1  A: 

This is an assignment for the 8-puzzle problem talked about using the A* algorithm in some detail, but also fairly straightforward:

http://www.cs.princeton.edu/courses/archive/spring09/cos226/assignments/8puzzle.html

Evan
A: 

Remember that A* will search through the problem space proceeding down the most likely path to goal as defined by your heurestic.

Only in the worst case will it end up having to flood fill the entire problem space, this tends to happen when there is no actual solution to your problem.

Triston Attridge