Wikispaces Classroom is now free, social, and easier than ever.
Try it today.
Pages and Files
N - Puzzle
Travelling salesman problem
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.
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.
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:
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.
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
Heuristics for the N-Puzzle
Nilsson's Sequence Score
Tiles out of row and column
Samples for 8-puzzle start boards can be found
An open source Java Applet for solving the 8/15-Puzzle with A*
help on how to format text
Turn off "Getting Started"