We still have a puzzle of even width, with the still in the second row starting from the bottom, and the number of inversions – 2 – has not changed at all!
If we try two swap the first two numbers we got this array: It has an even number of inversions which makes it unsolvable. the gap is in the second row starting from the bottom. Still, it could happen that we try that trick only to find out that our first 2 positions in the array include the gap: swapping them would do us no good. We have a 3×3 puzzle – odd with of 3 tiles- and an even number of inversions: 20. New total count of inversions: 6 + 6 + 4 + 2 + 2 = 20 inversions
So the next thing to try would be this: we can represent a Slide Puzzle as a one dimensional array, what if we used an algorithm to shuffle the array? Let’s study this approach next. If we repeat the process enough times we would end up with a seemingly reasonable shuffled puzzle, still it seems a cumbersome and inefficient approach. Using this approach it could happen that we select the same piece twice to move it forward and back, for example, so that we would be shuffling the puzzle in one move and returning it back to its original state the next: not what we want! We could solve that problemīy keeping track of the pieces we have already moved and selecting when possible one we have not moved yet. We start with a solved puzzle, we select randomly one of the possible pieces to slide and we move it, and we repeat the process N times. The simplest way to shuffle our puzzle would be what I call the manual process, since it kind of replicates the process we would use if instead of a software puzzle we were playing with a typical plastic toy one. In this post we are going to talk about the algorithm to shuffle the slide puzzle, and how this apparently simple process has a few surprises in store for an unaware developer. Have you ever considered how you would implement your own Slide Puzzle Game? If so you probably have considered stuff like the user interaction sliding the pieces around, how to check when the puzzle is solved, and how to shuffle the slide puzzle every time the user selects new game. Slide puzzles: simple, addictive and fun.
0 kommentar(er)
