How to optimally shuffle the fifteen puzzle, for all sizes?

Question

The problem is to generate 'fifteen' puzzles in varying sizes, ensuring that all puzzles are solvable. For testing a solvable puzzle, see Wikipedia or Wolfram.

Naive shuffle methods include (a) simulate a large number of random moves (b) shuffle somehow, check if valid, fix if not. See also How can I ensure that when I shuffle my puzzle I still end up with an even permutation?.

An optimal shuffle will (a) produce every possible solvable puzzle with equal probability (b) perform no more than N swaps, where N is the number of tiles, and most likely (c) leave the puzzle solvable after every swap.

Is there such a method?

---

There is a well-known method using steps (1) Knuth or similar shuffle (2) test for validity (3) make one more swap if needed. This amounts to 3 separate algorithms, and (because of step 3) does not produce every possible solvable puzzle with exactly equal probability. If there is no method that satisfies the requirements, then there should be a proof to that effect.

---

After further thought, step 3 may not harm the distribution of shuffles but it does (a) make the total number of shuffles uncertain (b) require an additional test. In the target application, the logic to do that test is not available.

So the question could be reformulated as finding a minimum set of swaps that generate every possible valid shuffle with equal probability. The final result must be a solvable puzzle with no need to test for solvability. Hypothetically the number of swaps needed is N-1.

Answer 1

There is a well-known method using steps (1) Knuth or similar shuffle (2) test for validity (3) make one more swap if needed. This amounts to 3 separate algorithms, and (because of step 3) does not produce every possible solvable puzzle with exactly equal probability.

I think your conclusion here is faulty. Here's a 3-step method:

1. Shuffle the grid normally.
2. Check if the grid is solvable.
3. If the grid isn't solvable, then swap the tile labeled 1 with the tile labeled 2.

First of all, there is a bijection between solvable grids and unsolvable ones, obtained by swapping tiles 1 and 2. Clearly, the shuffle in step (1) produces all grids with equal probability, but only half of these are solvable. So if we apply the bijection to all unsolvable grids, then we're left with a uniform distribution over solvable grids. (There are exactly 2 ways to "end" with any given solvable grid: either shuffle the grid into that state, or shuffle the grid into its unique corresponding unsolvable state. Clearly the probability of this is the same for every solvable grid.)

---

Proof of correctness

From the Wikipedia article on the 15 puzzle:

The invariant is the parity of the permutation of all 16 squares plus the parity of the taxicab distance (number of rows plus number of columns) of the empty square from the lower right corner. This is an invariant because each move changes both the parity of the permutation and the parity of the taxicab distance. In particular if the empty square is in the lower right corner then the puzzle is solvable if and only if the permutation of the remaining pieces is even.

From the Wikipedia article on the parity of a permutation:

An even permutation can be obtained as the composition of an even number and only an even number of exchanges (called transpositions) of two elements, while an odd permutation can be obtained by (only) an odd number of transpositions.

Hence, swapping (transposing) any two numbered tiles (not the empty square) will change the parity of the permutation (we added one transposition). However, the parity of the taxicab distance of the empty square is unchanged (since the empty square did not move).

Therefore, such an operation will change the solvability of the puzzle. In other words, applying this operation (e.g., swapping tiles labeled 1 and 2) will always transform an unsolvable puzzle into a solvable one and vice versa. (This operation is also a bijection because it is invertible.)

---

Proof that requirements (b) and (c) cannot be met simultaneously

Consider the starting 2x2 grid:

1 2
3 _

and the "goal" grid:

_ 3
2 1

Can we move from the first grid to the second grid, using at most 4 swaps (requirement (b)) and keeping the grid solvable after each swap (requirement (c))?

First, notice that the only allowable swap satisfying requirement (c) is to move the space _ with an adjacent tile (not the diagonal tile). By symmetry, we can just move the space clockwise without loss of generality. Performing any counter-clockwise swap is then useless since it cancels out the previous clockwise swap.

So we repeatedly swap the space with the adjacent tile in the clockwise direction until we obtain the desired grid. This takes 6 swaps. Since 6 > 4, requirement (b) cannot be met while satisfying requirement (c).

Answer 2

Assume a checkerboard colouring. Then starting with a solvable puzzle (permutation parity even) the following swaps are possible:

1. Any two numbers: parity is reversed.
2. A space with any number on a square of the same colour: parity is reversed.
3. A space with any number on a square of the opposite colour: parity is unchanged.

The puzzle can only be made valid at every step (parity even) if the only swaps are of type 3. If each swap of type 1 or 2 is followed by another of the same type then the puzzle will be valid after each such pair.

A sufficient number of swaps chosen randomly from the above will achieve a high degree of disorder. A total of 16 swaps, such that every square is swapped at least once and obeying these swap rules should be sufficient. It is hard to determine whether the distribution of puzzles is perfect, but it should be good enough for most purposes.

The solution generalises easily to puzzles other than 4x4.

Answer 3

• Start with the puzzle solved and the missing tile at the end
• Swap an even number of pairs (these should be non missing tiles). Do this a sufficient number of even times (nTiles^2*10 is good).
• The puzzle is still solvable at this point, but we want to move the missing tile.
• Scoot the missing tile back up the puzzle a random number of times based on the total number of tiles. To "scoot back" you can't go in reverse reading order. You need to swap tiles in a zig-zag pattern backward along the array, just as the missing tile would, inverting the direction every other row.

   function shuffleDeck() {
      let iters = nTiles * nTiles * 10
      for (let i = 0; i < iters; i++) {
        let i = floor(random(nTiles * nTiles - 1))
        let j = i
        while (i === j) j = floor(random(nTiles * nTiles - 1))
        swap(deck, i, j)
      }
      let end = nTiles * nTiles - 2
      let start = floor(random(end))
      for (let i = end; i >= start; i--) {
        let index = i
        let row = floor(i / nTiles)
        let inverted = (nTiles - row) % 2 === 0
        if (inverted) {
          index = ceil(i / nTiles) * nTiles //start at the end
          index -= i % nTiles + 1 //move backward
          if (index < row * nTiles) index += nTiles //wrap the left
        }
        swap(deck, deck.indexOf(-1), index)
    
      }
    }
    
    function swap(arr, i, j) {
      let buffer = arr[i]
      arr[i] = arr[j]
      arr[j] = buffer
    }

Answer 4

A very quick algorithm I call it 3-tile shift shuffle can do this: Randomly pick 3 tiles, shift them, and do it repeatedly for about only 5 times, you'll get a solvable mixed-up state of the puzzle.

I solely developed and proved it. And the proof of 3-tile-shift shuffle is solvable is pretty simple without much maths.

Here is the proof:

1. In a 2 * 2 range, for a 3-puzzle, three-title-shift state is resolvable.

2. In a 15 puzzle, given the state that only three tiles are shifted, with other tiles in there original position. We can move the three tiles into a 2 * 2 window, along with the empty position, thus form a 2 * 2 3-puzzle. We call the movement of all tiles in to this state as F movement.

3. Resolve the three tiles in their correct order in the 2 * 2 window.

4. Reverse the movement of F, i.e., F' movement to get all tiles to there original position. Now every tile is in its correct position.

I don't know if somebody else has developed this algorithm and published it somewhere before.

I firstly published this algorithm in Microsoft forum as an answer to a discussion of its puzzle widget, that's about approximately 10 - 15 years ago. But it seems it's only useful for puzzle programming, therefore, it is still unknown.