Puzzle del 15

The 15 Puzzle (also called the Fifteen Puzzle, Gem Puzzle, or Sliding Puzzle) consists of a 4x4 frame containing 15 numbered square tiles and one empty space. The tiles are scrambled, and the player must slide them one at a time into the empty space to arrange them in numerical order, typically from 1 to 15 reading left to right, top to bottom, with the empty space in the bottom-right corner. Only tiles adjacent to the empty space can be moved.

Rules

1. The board is a 4x4 grid with tiles numbered 1-15 and one empty space.
2. You can slide any tile adjacent to the empty space (up, down, left, or right) into the empty space.
3. Only one tile can move at a time.
4. The goal is to arrange all tiles in order: 1-4 in the top row, 5-8 in the second, 9-12 in the third, and 13-15 in the fourth, with the empty space at position 16 (bottom-right).

Strategies

• Solve Row by Row: First solve the top row (1-4), then the second row (5-8), then the remaining tiles.
• Corner Technique for Top Rows: To place a tile in the top-right corner without disturbing already-placed tiles, use a specific sequence: position the target tile in the second row, then slide the corner piece down and the target piece in simultaneously.
• Last Two Rows Together: When solving the third row, you must work on both the third and fourth rows simultaneously, as placing bottom tiles in isolation is impossible.
• 3-2-1 Approach: When near completion, work on the last three tiles together, rotating them into position.
• Count Inversions: Not all configurations are solvable. The puzzle is solvable if and only if the number of inversions (pairs of tiles in wrong relative order) plus the row number of the empty space (counting from bottom) is even.
• Minimize Moves: Advanced solvers aim for the fewest moves possible. The optimal solution is NP-hard to compute, but heuristics like the Manhattan distance (sum of each tile's distance from its goal) give good estimates.

The 15 Puzzle has one of the most colorful histories of any puzzle. It burst onto the scene in the United States around 1880, creating a nationwide craze comparable to the Rubik's Cube mania of the 1980s. For months, people everywhere — in offices, factories, and homes — were obsessed with sliding tiles into order.

The puzzle's origins are debated. For decades, the famous puzzle designer Sam Loyd claimed to have invented it, but modern research attributes the invention to Noyes Chapman, a postmaster from Canastota, New York, who created a version of the puzzle around 1874. Loyd's claim to the puzzle's invention, while unfounded, was instrumental in promoting it. Loyd famously offered a $1,000 prize to anyone who could solve a specific configuration where tiles 14 and 15 were swapped — a configuration that is mathematically impossible to solve, which Loyd almost certainly knew.

The mathematical analysis of the 15 Puzzle was one of the earliest applications of group theory to puzzles. In 1879, mathematicians William Edward Story and William Woolsey Johnson independently proved that exactly half of all possible configurations of the puzzle are solvable from a given starting position. This proof was a landmark in combinatorial mathematics.

The puzzle has endured for over 140 years and has been produced in countless variations — different sizes (3x3, 5x5), picture puzzles instead of numbers, circular and triangular versions, and digital implementations. The 8 Puzzle (3x3 version) became a classic problem in artificial intelligence, used to teach and benchmark search algorithms like A* and IDA*. The 15 Puzzle remains a standard topic in computer science courses, recreational mathematics, and competitive speedsolving.