13/09/2013

The n-puzzle is known in various versions, including the 8 puzzle, the 15 puzzle, and with various names (Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others). It is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. If the size is 3*3, the puzzle is called the 8-puzzle or 9-puzzle, and if 4*4, the puzzle is called the 15-puzzle or 16-puzzle. The object of the puzzle is to place the tiles in order (see diagram) by making sliding moves that use the empty space. The project aims to produce an automatic algorithm, given a valid input, find the potentially best solution to the problem.