zoranh

n-Puzzle is a matrix of tiles with one tile missing, as given in the following picture:

Most notorious n-puzzles are 8-puzzle (3x3 tiles) and 15-puzzle (4x4 tiles).

Solving the n-puzzle is a typical informed search problem. It is search problem because program solving the puzzle must search through valid states of the puzzle in order to find a sequence of moves that transform a puzzle from any valid starting position into the solved state. It is informed search because program is aware of all aspects of the puzzle, like physical fact that once you move a tile downwards, a hole (missing tile) goes upward. In informed search strategies, solver can use such knowledge of the system to implement more efficient search, as opposed to uninformed strategies (also called blind or naive search), where such knowledge is not available. Examples of blind search strategies are breadth- and depth-first search, which are basically brute force strategies.

To solve the n-puzzle efficiently, one can use A* search algorithm with appropriate admissible heuristic (definitions follow).

A* algorithm is one of the most powerful search algorithms and it is based on best-first decision strategy. The algorithm operates on "states" or "nodes", where each state is one (better-off unique) state of the puzzle. One must ensure that previously visited states are not calculated again (if reached via a different route than the first time), as to avoid possibly tremendously many steps that have already been processed before.

To each node a value is assigned, consisting of two components added together:

• Path length traversed to reach that node - in n-puzzle problem this is total number of moves made from the starting position until this position was reached.
• Admissible heuristic estimate of the rest of the route - this is the estimate of how many steps there are remaining to solve the puzzle.

In each step of the algorithm, one node is taken such that its value is the smallest of all values assigned to all nodes currently in processing (these nodes are called unexpanded). If more than one node have the same minimum value assigned, just pick one (any decision is right). When a node is selected (and removed from the collection), it is expanded by performing all valid moves from that state. This will lead to creating as many new states of the puzzle as there were valid moves from current state. Now one should inspect these states and, if any of the states has not been previously inserted into the collection, insert it. Then the step repeats itself. Algorithm terminates when solved state is reached.

Term admissible heuristic means that it is a heuristic function that never overestimates the cost of the remaining part of the solution. It means that it never states that number of steps to solve the puzzle is going to be greater than it really is, i.e. it is optimistically saying that solution is nearer than it is. Reason is simple - suppose that this is not the case, and that heuristic may say that path to the solution is farther away than it is. Then algorithm will not take that node into consideration until all other nodes are considered first, which leads to creating exponentially many new nodes, further leading to endless search and the low-light of all A* algorithms called - A* often stays out of memory long before it stays out of time.

Two admissible heuristics can be suggested to be applied when coding A* solution to n-puzzle problem:

• Total number of misplaced tiles - in this case, any tile which is not in its goal position counts as one, and tile which is in its goal position counts as zero. In 8-puzzle, value of this heuristic goes from 8 (totally unsolved puzzle) up to 0 (solved puzzle).
• Sum of all distances of tiles from their goal positions - for each tile distance from goal position is sum of horizontal and vertical distances from goal position (calculating diagonal distance would be pointless because tiles do not move diagonally).

This article continues with in-depth analysis of search strategies applied to discrete games, also posted on CodeCall forum at this address:
Applying Search Algorithms to Turn-Based Games

For more information on this topic, refer to:
A* Search Algorithm article on Wikipedia
S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, 2nd Edition, pp. 105-110.