title: How can I ensure that when I shuffle my puzzle I still end up with an even permutation?
body: <p>I'm interested making an implementation of the <a href="http://en.wikipedia.org/wiki/Fifteen_puzzle" rel="nofollow noreferrer">14-15 puzzle</a>:
  <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/15-puzzle.svg/400px-15-puzzle.svg.png" alt="alt text"></p>
  
  <p>I'm creating an array with the values 0 - 15 in increasing order:</p>
  
  <p>S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }</p>
  
  <p>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.</p>
  
  <p>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?</p>
  
  <p>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?</p>