Why half of all shuffled 15-puzzles can't be solved (and two ways to fix it in JavaScript)

The 15-puzzle looks like the easiest game to code. Fifteen numbered tiles, one gap, slide tiles into the gap until the numbers are in order. Most first versions shuffle the tiles like this:

const tiles = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]; // 0 is the gap
tiles.sort(() => Math.random() - 0.5);

It works, the board looks scrambled, and about half of your players will be stuck forever. No sequence of moves will ever solve their board. Here's why, and two clean ways to make sure every board you generate can be solved.

The rule hiding in the puzzle

Write the tiles out in reading order, skip the gap, and count inversions: pairs where a bigger number comes before a smaller one. In 2 1 3 4 … there is one inversion (2 before 1).

Now think about what a move does to that count.

• Sliding a tile left or right doesn't change the reading order of the numbers at all, so the inversion count stays the same.
• Sliding a tile up or down moves it past the other tiles in its row: on a 4×4 board that's three tiles. Each one it passes either gains or loses an inversion, so the count changes by 3 or 1 — an odd number. At the same time, the gap moves one row.

So on a board with an even width, every vertical move flips two things together: the parity (odd/even) of the inversion count, and the parity of the gap's row. That means this sum never changes parity, whatever you do:

inversions + (gap row counted from the bottom, starting at 1)

On the solved board there are 0 inversions and the gap is on the bottom row (1), so the sum is odd. Any board where it's even can never reach the solved state. A random shuffle lands on each kind about half the time.

On boards with an odd width (3×3, 5×5) a vertical move passes an even number of tiles, so the gap's row doesn't matter: a board is solvable exactly when the number of inversions is even.

Fix 1: check the shuffle, and repair it

Shuffle properly (Fisher–Yates, not sort), then test the rule above:

function countInversions(tiles) {
  const nums = tiles.filter((n) => n !== 0);
  let count = 0;
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++)
      if (nums[i] > nums[j]) count++;
  return count;
}

function isSolvable(tiles, size) {
  const inv = countInversions(tiles);
  if (size % 2 === 1) return inv % 2 === 0;
  const gapRowFromBottom = size - Math.floor(tiles.indexOf(0) / size);
  return (inv + gapRowFromBottom) % 2 === 1;
}

If the board fails the check, you don't need to shuffle again. Swapping any two numbered tiles changes the inversion count by an odd number, which flips the parity and makes the board solvable:

function shuffledBoard(size) {
  const tiles = [...Array(size * size).keys()].slice(1).concat(0);
  for (let i = tiles.length - 1; i > 0; i--) {             // Fisher–Yates
    const j = Math.floor(Math.random() * (i + 1));
    [tiles[i], tiles[j]] = [tiles[j], tiles[i]];
  }
  if (!isSolvable(tiles, size)) {
    const [a, b] = tiles.map((n, i) => (n ? i : -1)).filter((i) => i >= 0);
    [tiles[a], tiles[b]] = [tiles[b], tiles[a]];            // swap the first two numbered tiles
  }
  return tiles;
}

This is fast and gives every solvable arrangement an equal chance.

Fix 2: never break the rules in the first place

The other approach is even simpler to trust: start from the solved board and make a few hundred random legal moves. Every board you reach that way is solvable by definition, because you could play the moves backwards.

function scramble(size, steps = size * size * 12) {
  const tiles = [...Array(size * size).keys()].slice(1).concat(0);
  let gap = tiles.length - 1, last = -1;
  for (let k = 0; k < steps; k++) {
    const r = Math.floor(gap / size), c = gap % size;
    const options = [];
    if (c > 0) options.push(gap - 1);
    if (c < size - 1) options.push(gap + 1);
    if (r > 0) options.push(gap - size);
    if (r < size - 1) options.push(gap + size);
    const choices = options.filter((i) => i !== last);      // don't undo the previous move
    const next = choices[Math.floor(Math.random() * choices.length)];
    [tiles[gap], tiles[next]] = [tiles[next], tiles[gap]];
    last = gap;
    gap = next;
  }
  return tiles;
}

Two details matter. Skipping the move that would undo the last one stops the walk from wasting steps going back and forth. And you want enough steps: around 12 per cell gives a well-mixed board on 4×4. If you want to be safe, check that the result isn't accidentally solved and keep going if it is.

Which should you use? Fix 1 is mathematically uniform. Fix 2 needs no theory at all and is hard to get wrong. Both are a few lines.

Bonus: slide a whole row with one tap

Once the shuffle is right, the next thing players notice is input. On a real 15-puzzle you can push three tiles at once. In code: if the tapped tile is in the same row or column as the gap, walk from the gap towards the tile, moving each tile one step:

function slideTowards(tiles, size, cell) {
  const gap = tiles.indexOf(0);
  const sameCol = cell % size === gap % size;
  const sameRow = Math.floor(cell / size) === Math.floor(gap / size);
  if (cell === gap || (!sameCol && !sameRow)) return 0;
  const step = sameCol ? (cell > gap ? size : -size) : (cell > gap ? 1 : -1);
  let moved = 0;
  for (let i = gap; i !== cell; i += step) {
    [tiles[i], tiles[i + step]] = [tiles[i + step], tiles[i]];
    moved++;
  }
  return moved;   // count each tile as one move
}

It's a small change and the game immediately feels like the physical toy.

A complete version

If you want to see all of this in a finished game, with tile animation, touch, keyboard and swipe controls, a move counter and a timer, there's a free MIT-licensed one-file version you can play and read here: Slide 15 demo and its source on GitHub. It uses the random-walk approach (Fix 2). A longer walkthrough of the whole file is in this sliding puzzle tutorial.

Happy sliding, and may none of your players get the unsolvable half.