Nothing like jumping on the bandwagon a couple of years after it’s ridden off into the sunset. Today I would like to ramble on about the whole Harry Potter phenomena. For the sake of brevity and clarity, I will hereafter simply write “HP”. Even if you’ve never read any of the books nor seen any of the movies, surely you must have at least heard about him. (If not, what planet are you from?)
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.)
Godzilla. King of the Monsters. Owner of the longest movie franchise in history (take that, James Bond!). If you’ve never heard of him, you must’ve been living in a cave for the last 60 years. Whether you’re a cave-dweller or not, I’m going to give you a little history lesson so that we’re all on the same page. (Emphasis on “little”; I highly recommend reading the Wikipedia articles on both the character and franchise!)
“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.
Hello, world. This is my first post on my new-fangled WordPress blog thingy. I am here because I no longer have any other personal presence on the Internet. I used to have a personal web page with my ISP, Comcast, until they killed that practice. Before that, I used to have a GeoCities site until Yahoo! killed that. Before that was 1994 and I was (barely) on the Internet using a 9600 baud modem.
Why did it take me so long to do this? Because I’m lazy. Next question.
I was going to title this post “F1RST P0ST” in homage to xkcd 269, but decided against it because I can’t stand when people intentionally misspell English. Some people might refer to me as a “grammar Nazi”. Those people are idiots.
So why “Hello, world”? Well, for one it’s literal; I am saying hello to the (Internet) world with this post. For another, I am a programmer (for certain values of “programmer”) and traditionally one’s first program is a “Hello, world” program. Thirdly, I’ve already wasted far too much time trying to come up with a name for this stupid place and I didn’t want to waste any more coming up with a witty and clever name for this post. It’s not like anyone but me is ever going to read this site, anyway.
So, what am I going to be doing here? You got me. This might even be my only post here ever. When I came up with this idea, I figured I would post about whatever tickled my fancy. I have a wide range of interests, most of which would drive people away in droves, if there were anybody here. It seems to me that most successful blogs focus on one or a few core themes. I believe this is because the further you stray from the central idea that brought people to your site, the more people you alienate who disagree with you on those other topics.
Having said all that, I don’t think I will focus on only one theme, at least not at first. We’ll see how it goes. If anyone ever actually reads this, feedback would be appreciated.
So, who am I? No one. I choose to remain anonymous, at least for the time being. Rest assured that I am no one who is famous or has any sort of political, monetary or religious power.
So, what’s with the name? You try coming up with a name some time! You can read all about Sisyphus here. Of course, if you received a proper education, you already knew who he was. I chose that name to reflect my attitude towards writing this blog, as well as my other hobbies.
Just what are those hobbies?
I’ve already mentioned I’m a programmer. Technically, I am (or at least was, briefly) a professional because I once
prostituted myself got paid to write a serious application for a customer. Also, when I was gainfully employed as a computer technician, I wrote several programs that aided me in my work. Nowadays, I program for fun. I’ve been programming since 1982, although I was interested in computers long before that.
There are more hobbies, and I might get to them if I ever post again. For now, I think I’ll end here and post this to see how this thing works.