How can I ensure that when I shuffle my puzzle I still end up with an even permutation?

Question

I'm interested making an implementation of the 14-15 puzzle:

I'm creating an array with the values 0 - 15 in increasing order:

S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

Now, what I want to do is shuffle them to create a new instance of the puzzle. However, I know that if I create a board with an "odd permutation" than it is unsolvable.

Wikipedia says I need to create the puzzle with an even permutation. I believe this means that I simply have to do ensure I do an even number of swaps?

How would I modify Fisher-Yates so I ensure I end up with an even permutation at the end? If I do a swap for every element in the array that would be 16 swaps which I believe would be an even permutation. However, do I need to be concerned about swapping with itself? Is there any other way to ensure I have a valid puzzle?

Answer 1

I wouldn't really try altering the algorithm itself, it's probably moot for this application anyway. From what I see there are two options:

1. Just re-shuffle until you get an even permutation. This would probably throw away half a permutation on average (well, maybe a little more), but the extra work is very likely negligible.
2. Shuffle the board by using the game's moves itself. That is, just do a few hundred random moves. Since you're not taking all pieces out and re-assembling them you can't generate a state that's impossible to solve.

Answer 2

Fisher-Yates depends on the ability to swap any element with any other element. Since this violates the physics of the puzzle, I don't think you can use it here.

The naive solution is to do what you would do manually, randomly select one of the tiles adjacent to the empty one and swap with it. I don't know how many swaps you'd need to do to get a good shuffle.

Answer 3

You should be able to use Fischer-Yates.

• Generate a random permutation using Fischer-Yates.
• Check if it is even.
• If it is not even, swap the first two elements of the permutation.

Consider an even permutation P = x1 x2 .... xn.

Fischer yates generates P with probabilty 1/n!.

It generates x2 x1 ... xn with probability 1/n!.

Thus the probability that the above process generates the permutation P is 2/n! = 1/(n!/2)

n!/2 is the number of even permutations.

Thus the above process generates even permutations with same probability.

To check if a permutation is even: count the parity of the number of inversions in the permutation.