How can I make sure that when I shuffle my puzzle, I still get an even permutation?

Question

I am interested in making a 14-15 puzzle implementation:

I create an array with values ​​0 - 15 in ascending 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 puzzle instance. However, I know that if I create a board with an “odd permutation”, than it is unsolvable.

Wikipedia says I need to create an even permutation puzzle. I believe this means what I just have to do to ensure an even number of swaps?

How do I change Fisher-Yates, so I guarantee that in the end we get an even permutation? If I make a swap for each element of the array, which will be 16 swaps, which I believe will be an even permutation. However, do I need to worry about exchanging myself? Is there any other way to make sure I have a valid puzzle?

Answer 1

You can use Fischer-Yates.

• Create a random permutation using Fischer-Yates.
• Make sure it is even.
• If not, replace the first two elements of the permutation.

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

Fisher yates generates P with probability 1 / n !.

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

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

n! / 2 is the number of even permutations.

Thus, the aforementioned process even generates permutations with the same probability.

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

Answer 2

Here is what I found already here:

"This problem basically boils down to running a standard shuffle algorithm with a little twist.

The main observation is that for the solvability of the 15 puzzle, the parity of the permutation and the parity of the empty square must be the same.

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

The advantage of using a Knuth shuffle (or Fisher-Yates shuffle) is that it includes a number swap, so you can easily track the parity of the permutation. Each swap either keeps parity (if you change 1 and 3), or changes parity (if you change 1 and 2).

Place the empty square on the same parity as the parity of the permutation, and you're done. If the permutation has odd parity, put an empty space (1,3,5, ... is selected randomly). If the permutation has even parity, put a space on an even square.

In addition, "In practice, approximately every 4 successively created permutations will consist of two even and two odd permutations, so even the cost of each iteration is negligible."

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

Answer 3

I would not try to change the algorithm itself, it will probably still discuss this application. From what I see, there are two options:

• Just shuffle until you get an even permutation. That would probably pick half the permutation on average (well, maybe a little more), but the extra work is very negligible.
• Shuffle the board, using the game, moves itself. That is, just make a few hundred random movements. Since you do not remove all the parts and collect them, you cannot create a state that cannot be solved.

Answer 4

Fisher-Yates depends on the ability to exchange any item with any other item. 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 do manually, randomly select one of the fragments next to the empty one and share it. I do not know how many swaps you need to do to get a good shuffle.

Answer 5

UPDATED RESPONSE:

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

Inversion: a pair of objects that are in the opposite order from where they should be. For more information on inversions, see Counting Inversions in an Array

The polarity of the puzzle is whether the total number of inversions among all fragments is even or odd. A puzzle with 10 inversions even has polarity; a 7 inversion puzzle has an odd polarity.

Consider a 3x3 puzzle as follows:

| 6 | 3 | 2 |

| .. | 4 | 7 |

| 5 | 1 | 0 |

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

If the width of the puzzle is an even number, then moving the tile up or down will change the polarity, so it is important that the puzzle even has polarity when the empty tile is in the last row. To do this, we will add the distance from the empty tile from the bottom line to our common inversions.

Now we know that the puzzle is solvable, it even has polarity (or permutations). Therefore, if our polarity is even then, our problem is solved, but for odd polarity we must do this:

If the empty tile is not in the first row, replace the first two adjacent tiles in the first row. This will change the polarity by 1, and we will have a resolved puzzle that even has polarity.

But if the empty tile is in the first row, then swap adjacent tiles in the last row. This would make the puzzle solvable. Therefore, in the end you always get a solvable puzzle.

Hope I answer stackoverflow requirements for this question. Any doubts are welcome. Thanks.