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

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.

Answer 2

Here's what I found already answered here:

"This problem basically boils down to doing a standard shuffle algorithm with a small twist.

The key observation is that for the 15-puzzle to be solvable the parity of the permutation and the parity of the blank square must be the same.

First create a random permutation using a standard algorithm for that purpose. For example the Knuth shuffle algorithm: Random Permutations

The advantage of using Knuth's shuffle ( or Fisher-Yates shuffle ) is that it involves swapping numbers, so you can easily keep track of the parity of the permutation. Each swap either keeps the parity ( if you swap 1 & 3 ), or changes the parity ( if you swap 1 & 2 ).

Place the blank square on the same parity as the parity of the permutation, and you are done. If the permutation has odd parity then place the blank an odd square (1,3,5,... chosen at random ). If the permutation has even parity then place the blank on an even square."

Also, "In practice, roughly every 4 consecutively generated permutations will consist of two even and two odd permutations, so even the per-iteration cost is negligible."

You can also check this site out: http://eusebeia.dyndns.org/epermute

Answer 3

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 4

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 5

UPDATED ANSWER:

Before I introduce this algorithm, I need to define two terms: inversion and polarity.

Inversion: A pair of objects that are in the reverse order from where they ought to be. For more information on inversion, refer Counting inversions in an array

Polarity of a puzzle is whether the total number of inversions among all tiles is even or odd. A puzzle with 10 inversions has even polarity; a puzzle with 7 inversions has odd polarity.

Consider 3x3 puzzle like this:

| 6 | 3 | 2 |

| .. | 4 | 7 |

| 5 | 1 | 0 |

Counting all inversions here, we get: (i) 6 is inverted with 0, 1, 2, 3, 4 and 5. (ii) 3 is inverted with 0, 1, and 2. (iii) 2 is inverted with 0 and 1. (iv) 4 is inverted with 0 and 1. (v) 7 is inverted with 0, 1 and 5. (vi) 5 is inverted with 0 and 1. (vii) 1 is inverted with 0. In total we have 19 inversions.

If the width of puzzle is even number then moving a tile up or down will reverse the polarity so it is important that the puzzle is having even polarity when the empty tile is in last row. For this we will add the distance of the empty tile from the bottom row to our total inversions.

Now we know that a puzzle is solvable if it has even polarity (or permutations). So if our polarity is even then our problem is solved but for odd polarity we have to do this:

If the empty tile is not in the first row, then swap first two adjacent tiles in first row. This will change the polarity by 1 and we will have solvable puzzle having even polarity.

But if empty tile is in first row then swap adjacent tiles in last row. This would make puzzle solvable. So at the end you always end up with a solvable puzzle.

I hope I satisfy the answering requirements of stackoverflow for this question.