It’s been a while

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.)



Wherein I say something

“Something.”  Hah, hah, fooled you!

Seriously though, it’s been a few months since I set this thing up, so I figured I had better post something before they delete the account for inactivity.

What have I been doing all this time?  Getting closer to death, for one.  Hmm, that about sums it up.  No, I have been doing something constructive (for certain small values of “constructive”):  I have been going back and redoing all of my Project Euler problems.

For those of you who don’t know what Project Euler is, I’m not going to bother explaining it.  The rest of you may ask, “Why redo them?”  Because I’ve been playing around with FreeBASIC and I wanted to try out my programming chops using it.  Yeah, yeah, I know BASIC is a toy language and that serious programmers don’t use it.  It’s a good thing, then, that FB is an extended version of QuickBASIC, which itself I don’t really consider a “true” BASIC.  BASIC uses line numbers and GOTOs, people.  FB (and QB) may use the same keywords, but I do not consider either of them (or VisualBASIC) as BASICs.  Having said all of that, and powerful as FB is, it is still crippled by its forced “backwards-compatibility” with its true BASIC ancestors.  In other words, it’s much better than BASIC but still not an ideal programming language.

Why use it then?  For one, it’s free.  As in “Free”-BASIC, get it?  Two, it produces native 32-bit code.  Three, it has a true 64-bit integer type.  Four, it allows the use of inline assembler using Intel syntax.  (See here.)  The Pascal compiler I have been using produces 32-bit code, but that code is in a 16-bit DOS executable with a DOS extender.  I’ve looked at FreePascal, and it’s pretty good, but it has some shortcomings:  even though it is a 32-bit compiler, Integers are still 16-bit by default; there is no native 64-bit integer type; there is no GUI IDE; worst of all, inline assembler requires AT&T syntax!.  (Note:  I haven’t looked at FP in a long time; some of those problems may have gone away since then.)

So along the way I’ve learned quite a bit about how to properly program in FB, although there are still some things which elude me.  Hopefully I’ll be able to pick up those things if I keep at it.

As a historical note, when I first started Project Euler (PE from now on), I used Turbo Pascal 6.  That is a DOS-based 16-bit compiler with a 64KB limit on variables.  That’s total, not each!  You can use the heap to create dynamic variables, but they are all limited to 64K each, and the heap itself only uses base memory so its maximum size is about 600KB.  It was easy enough to solve all of the simple problems with it, but when I started encountering problems that simply required buffers and variables in the multi-megabyte range, I moved on.

Another reason I have been redoing PE problems is that I’ve pretty much gone as far as I can go with it.  I’ve solved 213 out of 556 (as of today) problems, and I don’t think I can solve very many more, if any, without outside help.  In other words, I’ve solved all of the easy and middling problems.