N - Puzzle

The N-Puzzle is known in finite versions such as the 8-puzzle (a 3x3 board) and the 15-puzzle (a 4x4 board), and with various names like "sliding block", "tile puzzle", etc.

Description: The N-Puzzle is a board game for a single player. It consists of (N^2- 1) numbered squared tiles in random order, and one blank space ("a missing tile"). The object of the puzzle is to rearrange the tiles in order by making sliding moves that use the empty space, using the fewest moves. Moves of the puzzle are made by sliding an adjacent tile into the empty space. Only tiles that are horizontally or vertically adjacent to the blank space (not diagonally adjacent) may be moved.

Solvability: Half of the initial states for the N-Puzzle are impossible to resolve. This can be proved by an invariant of the board: The parity of permutations of all squares + the parity of the Manhattan distance of all squares. This is an invariant because each legal move changes both the parity of the permutation and the parity of the Manhattan distance. This invariant split the space of all possible states into two equivalence classes of solvable and unsolvable states. An O(N^2) algorithm to decide when an initial state of the N-puzzle is solvable can be found here: http://cseweb.ucsd.edu/~ccalabro/essays/15_puzzle.pdf

Algorithmic Problem:
Input: N*N board with (N^2 – 1) numbered tiles and one blank space – representing an initial state.
Output: a shortest sequence of moves
that by following those moves all tiles will be in their goal positions.

Algorithmic Solution: It has been proved that finding the solution of the general N-Puzzle is NP-complete (Ratner & Warmuth, 1986 ). The best known algorithm for solving the finite 8-puzzle version of the problem optimally is A*. Commonly, the heuristic employed in an A* search is the Manhattan Distance.

Heuristics for the N-Puzzle:

Samples for 8-puzzle start boards can be found here

An open source Java Applet for solving the 8/15-Puzzle with A*