Well, it’s been a while so I figured I had better post something new. Actually, I’ve been meaning to post something for quite some time now, I’ve just never gotten around to it. And, I’ve never gotten around to it because I never really had anything that I really wanted to say. Not that I do now; it’s just that, as I just said, I haven’t posted in a long time and I figure I had better post something.
So, in lieu of anything better, I’m going to write about my most recent little project. A few months ago I wrote a simple little game that Wikipedia says is called the 15-puzzle. I’m sure you are all familiar with it under whatever name you happen to call it. That’s what I’m going to talk about today. I chose this topic partly because I need to show some math and I wanted to figure out how to do that using WordPress.
When writing the game, I installed a feature to “shuffle” the tiles randomly. What my program actually does, however, is randomly move tiles a certain number of times (based upon the chosen difficulty level) from the final position. I wondered two things: 1) How many random moves were “enough” to guarantee a completely random arrangement and 2) Is there some algorithm for randomly placing the tiles such that the puzzle is still solvable?
Before I go any further I need to introduce some terminology so we don’t get confused. I have already called each piece a tile. There is also one empty space. All of the tiles and the one space occupy the rectangular grid. Each place occupied by a tile or the empty space is a cell. We will refer to grids as being m×n, and we will for the sake of convenience assert that m ≤ n. Therefore, a m×n grid contains
m×n cells which are occupied by
m×n-1 tiles and one empty space. We will call the number of cells Τ, so
Τ = m×n. For the 15-puzzle,
m = n = 4, so the grid is
4×4 and there are
Τ = 4×4 = 16 cells and
Τ-1 = 15 tiles. (Hence the name.)
Since the 15-puzzle uses a 4×4 grid, there are 16! = 20,922,789,888,000 possible arrangements. According to Wikipedia, it has been proven that half of these possibilities can be reached, the other half cannot. (This holds true for any rectangular grid.) Therefore, there are 10,461,394,944,000 valid arrangements of the puzzle.
It turns out that any of those arrangements can be reached from the unshuffled starting position by no more than 80 moves! Unfortunately, there is no neat and tidy formula for computing this value; it must be empirically determined. But, it got me thinking: is there a simple way to come up with a ballpark figure for any arbitrary sized grid? I believe I have come up with such a way, by estimating how many possible positions are reachable after each move. Once the total number of positions reachable meets or exceeds the known number, we have our guess. Since in reality we overestimate how many positions we can reach, our guess will always be an underestimate of the number of moves necessary. Therefore, it will serve as a lower bound for the actual minimum number of moves necessary.
Remember, on each move we slide a tile into the empty space; we can instead think of this as sliding the empty space onto a tile. For most of the cells, we can “move” the empty space onto any of four adjacent tiles. Therefore, our first guess will be that for every possible current position, there are four times as many positions that can be reached on the next move.
A better guess takes into account the fact that the edge tiles can only be moved into three other tiles, and the corners onto only two. What we now have to do is sum up all of these possibilities and divide by Τ to get our multiplier. Looking back, we actually had to do this for our first guess too, but since all of the tiles were “4”, once we summed up 4 Τ times and then divided by Τ, we got 4 back. There are
(2×(m-2))+(2×(n-2)) cells that have 3 moves, and 4 cells (the corners) that have only 2 moves. All of the other cells,
(m-2)×(n-2), still have 4 moves. Therefore, after each turn we need to multiply our previous count of positions by
4×(m-2)×(n-2) + 3×((2×(m-2))+(2×(n-2))) + 2×4, then divide by Τ. This equation simplifies to
4×m×n - 2×m - 2×n.
That’s pretty good, but we can go one better with the exact same amount of effort. You see, although each position can produce one of either 2, 3 or 4 new positions, they actually aren’t all new. One of them has to be the position we came from. Therefore, if we do the same thing as before but instead of 2 (for corners), 3 (for edges) and 4 (for interiors), we use 1, 2 and 3, we will get our best estimate yet. Replacing the values in the previous equation and simplifying it, we get
3×m×n - 2×m - 2×n.
A quick note is in order here. Obviously, any grid where
m = 2 will not have any interior cells; they will all be corners or edges. The math actually works out, though, because
m - 2 = 0, so we multiply by zero and get zero in return.
This post is already running too long, so I’m going to cut this short and show my results:
Puzzle Our guess Multiple Actual Ratio 2x2 (3) 6 1/1 6 1.000 2x3 15 21 2x4 22 36 2x5 29 55 2x6 36 80 2x7 44 108 2x8 52 140 3x3 (8) 22 5/3 31 1.409 3x4 31 53 3x5 41 84 3x6 51 95-130 3x7 62 96-177 3x8 73 123-237 3x9 85 150-322 4x4 (15) 43 2/1 80 1.860 4x5 56 107-138 4x6 70 132-208 4x7 85 149-290 4x8 100 188-384 4x9 116 227-490 5x5 (24) 73 11/5 152-208 2.082-2.849 5x6 90 177-297 6x6 (35) 112 7/3 230-423 2.054-3.777 7x7 (48) 162 17/7 352-752 2.173-4.642
All of the values in the “Actual” column were obtained from a page linked to from the Wikipedia article. (That link is actually to the WayBack Machine version of the page.)
Let’s go back to my original questions. I asked how many random moves were enough to guarantee a completely random arrangement. If by completely random arrangement we mean any of the
16!/2 possible positions, then we must make at least 80 moves.
Of course, just making 80 moves doesn’t guarantee that it will take 80 moves to return to the final position, since some of them might undo a previous move. At the time I wrote the game I hadn’t looked up any of this information and I just made my highest difficulty level make 119 moves. I arbitrarily chose this value because the program shows the moves being made and that was the longest I could sit still while it was making those moves. (I show the moves being made so that on the easier levels you could try to memorize them and undo them in order.) It looks like I should increase this value (and probably not show the moves to speed up the program on the higher difficulty levels) somewhat.
The other question I asked was is there some algorithm for randomly placing the tiles such that the puzzle is still solvable. Well, the Wikipedia article makes a statement about the parity of the puzzle determining this, but I couldn’t follow the math to determine exactly what they meant for this specific application. So, in other words, it looks like I will have to continue actually making valid moves from the final position to shuffle the game instead of randomly assigning tiles.
How about the ulterior motive for this post, figuring out how to show math? There doesn’t seem to be any sort of equation editor or anything like that. In the end, I chose to use “<code>” tags to show the math, and I used the special character set to show mathematical symbols. All in all, not very satisfying. Now I will try one more thing with this post, and that is to attach both the game in its current basic form as well as the program that calculated the values in the above table. I will put them both in a ZIP file which you can download here. Nope, WordPress says I can upload documents, but it doesn’t allow me to for some reason. Maybe I’ll figure it out later. (OK, I created a Google account and put the file there. That link should now work.)