n-puzzle problem

Play the game here

Gameplay

The n-puzzle (most popularly known for the 8-puzzle problem or 15-puzzle problem) problem is a problem where we have at our disposal a k x k board with k*k-1(=n) numerated tiles and an empty spot. A tile adjacent to the empty piece can be moved to this position. The acceptable moves are up, down, left, right. The goal is, starting from a given board to reach a given board where all the titles starting from the top left are sorted in ascending order.
For example, the 8-puzzle

8		6
5	4	7
2	3	1

needs to reach the form:

1	2	3
4	5	6
7	8

Solution

This C implementation uses A* search to solve this problem using as heuristic the sum of the manhattan distance of all non-empty pieces from the blocks to their estimated goal positions.

• Data representation
  

We represent each puzzle by saving:

1. The puzzle itself
   
2. A pointer to the puzzle it was generated by (to print the solution)
   
3. The move that caused the generation of the puzzle (u-up, d-down, l-left, r-right)
   
4. The coordinates of the empty piece (for instant access when swapping pieces)
   

How the search works

• At first, we find the heuristic calculation of the first given puzzle (using the manhattan distance of every piece).
  
  
• When generating the possible puzzles of a certain puzzle, we first check if the move that caused the puzzle to come to its current form is the reverse action of the move we are trying to apply. For example, if a puzzle came to its current form by moving down the empty piece (or moving up a numerated piece), moving the empty piece up will cause the generation of the puzzle before moving down the empty piece. So, we ignore it.
  
  
• If the generation of the puzzle is successful, we fix the heuristic calculation of the new puzzle by adding the manhattan distance of the old empty, now occupied, piece and removing the manhattan distance of the now empty piece (once occupied by the old puzzle) to the manhattan distance of the old puzzle.

Examples

An example for sizes 3(8-puzzle), 4(15-puzzle), 5(24-puzzle) and 6(35-puzzle) is included at the directory examples. Configure the preferred size (by default 4) at the makefile and run make example for it to be solved.