15-Puzzle Online

The classic sliding puzzle that has challenged minds for over a century. Arrange the numbers in order by sliding tiles!

How to Play: Click on any tile adjacent to the empty space to slide it into that space. The goal is to arrange all tiles in ascending order from left to right, top to bottom, with the empty space in the bottom-right corner.

0
Moves
00:00
Time
4x4
Puzzle Size
Solvable
Medium
Solver Algorithm:
Heuristic:
Puzzle Solved!

Congratulations! You solved the 4x4 puzzle in 0 moves and 00:00!

Your solution efficiency: 0% of optimal moves.

Move History

Moves: 0

About the 15-Puzzle

The 15-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, or Mystic Square) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle was "invented" by Noyes Palmer Chapman, a postmaster in Canastota, New York, who is said to have shown friends, as early as 1874, a precursor puzzle consisting of 16 numbered blocks that were to be put together in rows of four, each summing to 34.

Mathematical Significance: The 15-puzzle is often used in computer science to teach state space search algorithms. It's also used in AI research as a benchmark problem for heuristic search algorithms. Determining whether a given configuration is solvable involves checking the parity of the permutation.

Solvability Condition

For a 4x4 puzzle (15-puzzle):

1. Count the number of inversions in the tile arrangement.

2. Find the row number of the empty space (counting from bottom).

3. If the grid width is odd, the puzzle is solvable if the number of inversions is even.

4. If the grid width is even, the puzzle is solvable if:

  - The blank is on an odd row from the bottom and number of inversions is even, OR

  - The blank is on an even row from the bottom and number of inversions is odd.

Solving Strategies

Layer by Layer

Solve the puzzle one row at a time from top to bottom. Complete the first row, then the second, and so on.

Corner Method

Start by solving the corners, then work on the edges, and finally the middle pieces.

Snake Method

Arrange tiles in a snake-like pattern from the top-left corner to the bottom-right.

Algorithmic Approach

Use specific move sequences (algorithms) to position individual tiles without disturbing already placed ones.

Mathematical Properties

Puzzle Size Number of Tiles Possible States Optimal Solution Length Difficulty Level
3x3 (8-puzzle) 8 181,440 31 moves max Easy
4x4 (15-puzzle) 15 10^13 (approx) 80 moves max Medium
5x5 (24-puzzle) 24 10^25 (approx) 205 moves max Hard
6x6 (35-puzzle) 35 10^41 (approx) ?? moves max Expert

Puzzle Variations

Classic 15-Puzzle: The standard puzzle with numbers 1-15 and one empty space. The goal is to arrange numbers in ascending order.

1

Picture 15-Puzzle: Instead of numbers, the puzzle uses pieces of a picture that must be arranged to form the complete image.

2

Word 15-Puzzle: Tiles contain letters that must be arranged to form words or sentences.

3

15-Puzzle with Forbidden Moves: A variation where certain moves between tiles are not allowed, adding additional constraints.

Frequently Asked Questions

No, only half of the possible configurations are solvable. Whether a configuration is solvable depends on the parity of the permutation and the position of the empty space. For the standard 15-puzzle (4x4 grid), a configuration is solvable if and only if the parity of the permutation of the 16 squares (including the empty space as the 16th piece) plus the parity of the taxicab distance (number of rows plus number of columns) of the empty square from the lower right corner is even.

For the 15-puzzle, the maximum number of moves required to solve any solvable configuration is 80 moves. This number is known as "God's Number" for the 15-puzzle. It was determined through extensive computer analysis that any solvable 15-puzzle can be solved in 80 moves or fewer.

The 15-puzzle is a classic problem in artificial intelligence and computer science because it represents a state space search problem. It's used to teach and test various search algorithms like breadth-first search, depth-first search, A* search, and heuristic functions. The puzzle's large state space (over 10 trillion possible states for the 15-puzzle) makes it challenging but manageable for demonstrating search optimization techniques.

Effective manual strategies include: 1. Solve rows sequentially: Complete the first row (tiles 1-4), then the second row (5-8), etc. 2. Corner-first method: Place tiles 1, 4, 13, and 16 in their correct positions first. 3. Snake method: Arrange tiles in order following a snake-like path from top-left to bottom-right. 4. Grouping method: Solve groups of tiles (like the first 8 tiles) before moving to the next group. 5. Learn move sequences: Memorize patterns for moving specific tiles without disturbing others.

The 15-puzzle was invented in 1874 by Noyes Palmer Chapman, a postmaster in Canastota, New York. It became a worldwide craze in 1880, similar to the Rubik's Cube craze a century later. In 1880, the puzzle was marketed by Matthias Rice who manufactured it with wood in Boston. The puzzle's popularity created a financial bubble with people mortgaging their homes to buy puzzles, and it even led to a New York court ruling that the puzzle was not patentable since it was "a mere trifle". The puzzle remains popular today as both a physical toy and a digital game.