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?

Solution 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.

Solution 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.

Solution 3

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.

Solution 4

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

Solution 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.

View more solutions

Comments

[wowest]

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.

[John La Rooy]

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

[Jonny]

Half of your links are dead.