How can I use the Fisher-Yates shuffle while ensuring my permutation is even?
- by Mithrax
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?
