The 15-Puzzle or Fifteen Puzzle is a type of sliding puzzle consisting of one frame with numbered square tiles. The tiles are arranged randomly in the frame with 1 tile missing. Other names for the Fifteen Puzzle include Boss Puzzle, Gem Puzzle, Mystic Square and Game of Fifteen. Similar kind of puzzles are available in various other sizes such as the 8-puzzle. Puzzles with 3×3 tiles are known as 8-puzzles and 9-puzzles while puzzles with 4×4 tiles are called 15-puzzles and 16-puzzles. These puzzles are named according to their number of tiles as well as the total open spaces in the frame. The tiles have to be moved by sliding them using the empty spaces in order to solve the puzzle. These types of puzzles are very useful for modeling algorithms using heuristics.

According to Johnson & Story, half of the n-puzzles are initially arranged in such a way which makes them unsolvable with any number of moves. The tile configuration functions are considered for doing this calculation. The configuration remains constant under all the valid moves. It is then used for partitioning all the possible labeled situations into 2 equivalence categories of unreachable and reachable states.

The total sum of the parity of permutation of the sum of all the sixteen squares and parity of the empty square's taxicab distance (the sum of the total rows and columns) from the low right corner. It is an invariant due to the fact that the permutation's parity and the taxicab distance's parity changes with each move. Puzzles that have the empty space in their lower right corner are solvable if only the permutation of other pieces is even.

The Fifteen Puzzle's symmetries constitute a groupoid (not group because it is not possible to compose all moves), which acts on configurations.

Noyes Palmer Chapman, a postmaster from Canastota in New York was the first person to invent this type of puzzles. Chapman is believed to have shown a similar puzzle to his friends in the year 1874. This puzzle had sixteen numbered blocks that had to be arranged in 4 rows with each row summing to 34. This version of the puzzle was improved and distributed to different places including New York and Syracuse by Noyes Palmer Chapman's son Frank Palmer Chapman. The puzzle game spread into a wider area via sundry connections. It reached Watch Hill in Rhode Island and Hartford in Connecticut. The students of the American School for the Deaf began making these puzzles and selling them in places like Boston, Massachusetts. Matthias Rice, the owner of a woodworking company in Boston then took interest in the puzzle and started making them in 1879. He also convinced a goods dealer to start selling these puzzles as the "Gem Puzzles". In the year 1880, a cash prize was announced by Dr. Charles Pevey of Worcester, Massachusetts for solving the Fifteen Puzzle.

Copyright (c) 2012 PLAYWITHBEB.COM. All rights reserved.