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 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?

Xl

this smells like compsci homework! – Abad

Its quite a common CompSci homework problem – Diskin

Answer 1

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.

Horner

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. – Saurel

Answer 2

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.

Schreiber

Half of your links are dead. – Gamy

Answer 3

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

Cowans

Answer 4

The graph theoretic way to solve the problem is to imagine every configuration of the board as a vertex of the graph and then use a breath-first search with pruning based on something like the Manhatten Distance of the board to derive a shortest path from the starting configuration to the solution.

One problem with this approach is that for any n x n board where n > 3 the game space becomes so large that it is not clear how you can efficiently mark the visited vertices. In other words there is no obvious way to assess if the current configuration of the board is identical to one that has previously been discovered through traversing some other path. Another problem is that the graph size grows so quickly with n (it's approximately (n^2)!) that it is just not suitable for a brue-force attack as the number of paths becomes computationally infeasible to traverse.

This paper by Ian Parberry A Real-Time Algorithm for the (n^2 − 1) - Puzzle describes a simple greedy algorithm that iteritively arrives at a solution by completing the first row, then the first column, then the second row... It arrives at a solution almost immediately, however the solution is far from optimal; essentially it solves the problem the way a human would without leveraging any computational muscle.

This problem is closely related to that of solving the Rubik's cube. The graph of all game states it too large to solve by brue force, but there is a fairly simple 7 step method that can be used to solve any cube in about 1 ~ 2 minutes by a dextrous human. This path is of course non-optimal. By learning to recognise patterns that define sequences of moves the speed can be brought down to 17 seconds. However, this feat by Jiri is somewhat superhuman!

The method Parberry describes moves only one tile at a time; one imagines that the algorithm could be made better up by employing Jiri's dexterity and moving multiple tiles at one time. This would not, as Parberry proves, reduce the path length from n^3, but it would reduce the coefficient of the leading term.

Recombination

Answer 5

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.

Bowfin

Answer 6

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.

Gothard

Answer 7

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

Crespo

Thanks that's my page! There is code for solving the 8puzzle and it's based on the treatment in Ivan Bratko's Prolog Programming – Strafford

Answer 8

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.

Baptista

Not really. An admissible heuristic merely needs to never overestimate the number of steps required. If you could tell which of two steps was closer, you would not be doing a search in the usual sense, just iterating through the steps as they got closer – Fran

Answer 9

For my current experience, on how to solve an 8 puzzle. it is required to create nodes. keep track of each step taken and get the manhattan distance from each following steps, taking/going to the one with the shortest distance. update the nodes, and continue until reaches the goal

Dannydannye