15 puzzle · 4×4 board
The classic fifteen puzzle: a number slide puzzle with fifteen tiles, one gap, and the board everyone has held at least once.
Tap or drag a tile next to the empty space to slide it. Arrow keys work too. Every shuffle is solvable.
Because it has fifteen numbered tiles on a 4×4 board of sixteen cells, with the sixteenth cell left empty. It is also called the fifteen puzzle, the Game of Fifteen, and in some countries the Boss puzzle or Mystic Square. It dates from the 1870s and caused a genuine craze in 1880.
The hardest positions take exactly 80 moves to solve optimally. This was established by exhaustive computer search and is known as God's number for the 15 puzzle. If sliding several tiles in one row or column counts as a single move, the number drops to 43. A typical shuffled board needs about 53 optimal moves.
16! = 20,922,789,888,000 arrangements, of which exactly half, 10,461,394,944,000, are solvable. A position is solvable when the number of inversions plus the row of the empty cell, counted from the bottom starting at 1, is odd. The solved board scores 0 + 1 = 1.
The trick is order, not speed. Fill the top row, then the left column, and you are left with a 3×3 puzzle. Fill its top row and left column, and you have a 2×2 corner that solves by rotation. The two rules that make it work: never break a finished row or column, and place the last two tiles of each line together using a short setup rather than one at a time.