Skip navigation

Tag Archives: n-puzzle

Remember my portfolio website? The one I mentioned here? Well, it’s now up and accessible at kode.skytreader.net. There isn’t much there yet because I tried to make it a point not to link to school work1 but please feel free to look around the various things I craft. The CSS should look good for all browsers except IE. This is my first attempt at tableless layout and, man, IE really is a pain in the ass to work with. The main domain (www.skytreader.net) uses tables, unfortunately.

In other news, I’ll be doing my thesis/special problems course this year. I don’t know how much time will I be able to squeeze in for personal projects. I expect {kode.play();}2 to be as much in thesis mode as me. In any case, I can still consider my thesis as a personal project, don’t you think?

(By the way, by some turn of events, I’ll be doing my thesis alone. At least, so long as the list of accepted students released by the research lab I applied to doesn’t change. I guess that just makes my thesis all the more a personal project.)

And as for my n-puzzle solver? I haven’t had time to look into IDA*, as I planned in my previous post. The time I spent working on it the past two weeks or so, I spent on ways researching how to decrease the heat generated by my laptop’s CPU. I’ve cleaned the dust bunnies and all but it still overheats to the point of auto-shut down even when I’m just browsing the web, though so far that has only happened in Windows Vista. I’m pretty adamant continuing to force my laptop to its limits since I’ll be doing my thesis this year and being laptop-less is the last situation I would like to find myself in.

(It’s been raining real heavy the past few days though and I noticed that my laptop is going easy on heating up. Could all those auto-shut down heat-ups be due to the hot summer weather? That’s funny since I had this laptop since last year’s summer and it didn’t auto-shut down at all then. And last year’s summer was way hotter, I tell you.)

Aside from my thesis, I’m taking my Artificial Intelligence course this semester. Maybe, hopefully, there really is still something I missed from A*. Having someone explain it to you really makes a lot of difference from self-studying. Hopefully, by semester-end, my n-puzzle solver can solve a randomly-generated solvable instance.

That’d be all for now. See you soon.

  1. Okay, this breaks for GradeGrid but I invested so much time in it it’s good as personal as well. []
  2. Yep, that’s the new official spelling :D []

It seems that I’m done coding the A* search of my n-puzzle solver. I spent almost all of last week doing it, as I discovered that there are some flaws in my understanding of A*.

The web doesn’t seem to have a lot of resources on A* compare to, say, graph algorithms. Google “a* search” and the only relevant link you’ll get is the first hit, a Wikipedia article at that. The second search hit, remarkably funny (for me, at least), is a search engine for cemetery records. The best search terms seem to be either “a* search algorithm” or “a* searching algorithm“. And even at that, not all the hits in page one have something to do with A*. Compare with, say, googling for “bellman ford” to find resources on the Bellman Ford algorithm. The best A* resource for beginner’s that I found on the the web will be this.

I said that my A* seems to work because I haven’t managed to make it solve randomly generated solvable instances yet; solving time takes too long that my computer heats up so much to the point of auto shut down. I’ve managed to get it to solve an instance with a Manhattan distance of 11 but I haven’t tried anything further than that yet (the randomly generated instances of size n=15 usually take a Manhattan distance of around 30, give or take).

I wonder how things would’ve went if I implemented my search in Java instead of Python. I remember, when I ran a (hopelessly inefficient) Java brute-force Sudoku solver in my old HP Pavilion DV1000 (default specs, i.e., Windows XP Home Edition, 1.5GHz processor, 512MB RAM), I managed to keep it up for hours, though, to make things fair, I did that in an air-conditioned room. For comparison, I ran my A* on a Gateway T-series (can’t give exact model as it is not available on surface inspection, sorry), running Ubuntu 10.04 (Lucid Lynx) with AMD Turion 64 X2 (approx 2GHz) processor and 2GB RAM, room temperature.

Maybe, I’ll look into Iterative Deepening A* next with some time.sleep lines thrown in the code to allow time for my system to cool down. Stay tuned.

This coming week, I’m ready to code the AI (or should I say A*? ~wink~~wink~) of my n-puzzle project. I know that it’s been two weeks since I told the world about it but it’s been a busy two weeks and, aside from it, I’m also doing a lot of other things in my after-internship hours; it’s actually been ready since last week.

I decided to represent the puzzle as a one-dimensional list (the Python array). While it may seem counter-intuitive to do that since the n-puzzle is a two-dimensional grid, I decided to do so since, from that representation, it’d be straightforward to count the number of inversions. Inversions, as I’ve mentioned in my previous post, are important in determining if a given configuration is solvable or not.

Aside from inversions, there are two more computations that I had to address, which, unfortunately, isn’t very straightforward with a flat list. The first is determining the polarity of a row (polarity means whether a number is odd or even); the other one is computing the Manhattan distance* between two tiles. To solve both, I had to resort to some index arithmetic.

Although a 2D array representation will save me the trouble of two computations, those two computations are still way lighter (just arithmetic and some loops) than flattening out a list and then computing inversions (two nested loops, unless I’m mistaken).

(Though it is possible to compute inversions on a 2D array, I find that tedious to code.)

The biggest problem I encountered so far is in randomly generating a solvable instance of the puzzle. A naive approach would be:

  1. Generate a random instance of the puzzle.
  2. If the instance generated is unsolvable, go back to step 1. Otherwise, you’re done.

Since there are n! possible configurations for the puzzle, and n!/2[1] of these configurations is unsolvable, the approach described above runs in O(n!) time.

Another naive approach will be:

  1. Generate the solved instance of the problem.
  2. Randomly make movements on the puzzle—this will make the puzzle unsolved (duh!).

But how many movements must I do to make an unsolved state that is difficult enough? Since the movements made are random, I am not sure that more movements == more entropy == more difficult puzzle. Worse, I may even end up on the solved state again. Sure I can add a 3rd step to check (whether the puzzle is unsolved or whether the puzzle is difficult enough** or both) but at this point I already find things too complicated that I am no longer willing to analyze the time complexity of the method discussed.

And the best method I came up with is to use the properties of a solvable instance which I discussed in my previous post regrading the n-puzzle. I only had to address two simple problems with regards to this approach: 1) inserting the blank on a row of given polarity, and 2) adding an inversion to a sequence. The first one just needed some index arithmetic. The second one is slightly more complicated (see http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html***).

To test the stuff I’ve been coding, I defined the __str__ method for my n-puzzle. And, of course, things look ugly and bothersome to check with straight-out printing. With straight-out printing, my grid will look like

2 9 14 3
11 0 8 5
13 10   7
1 12 6 4

This is where I decided to use string formatting. Formatting, I can get

2  9  14 3
11 0  8  5
13 10    7
1  12 6  4

From what I remember from Java, string formatting is hellishly ugly to code, kind of like regex only, I understand regex but not string formatting.

Java String Formatting: Code

formatter.format("%4$2s %3$2s %2$2s %1$2s", "a", "b", "c", "d")

To say: return the 4th argument padded to 2 characters the 3rd argument padded to 2 characters the second argument padded to 2 characters the first argument padded to 2 characters. See the API for the Formatter class.

Python 3 String Formatting: Code

"{3:2} {2:2} {1:2} {0:2}".format("a", "b", "c", "d")

To say the same thing. See PEP 3101.

(This only works in Python 3. And 2.6, if I’m not mistaken.)

The output isn’t character-per-character exact but isn’t Python’s syntax better?

That’d be all for now. Must start on my A* ~wink~ – The Chad Estioco

*Along with the Manhattan distance issue comes the problem of moving tiles, as though they’re in a 2D grid—they involve more or less the same index arithmetic.

**And I must take pains to define what is difficult enough.

***I already gave this link last time.

[1] Russel and Norvig. Artificial Intelligence: A Modern Approach. 3rd ed.

Way back during last semester break, I decided to master Python. I’ve had a little brush with Python during the last days of my high school but as my high school “Computer Science” education was actually more like a hodge podge of pretty but pointless tricks, that doesn’t really count as much; all my programs then were more or less hard codes with no organization whatsoever—I didn’t even know how to define functions save in Java and JavaScript.

Solved configuration of the 15-puzzlr

Taken from Wikipedia

Anyway, to learn Python, I decided to tackle the n-puzzle problem. I guess you’ve seen them as a kid, those mxm* set of tiles (m = 4, usually) with one tile missing so that you can move the tiles around. The problem is simple: generate the sequence of movements needed to solve the puzzle. Pictured at the right is the solved configuration of the 15-puzzle.

On my first try, I delved into the math involved in checking whether a given initial configuration is solvable. Yep, there are unsolvable initial configurations. Interchange the “15” and “14” tiles in the image at the right and you get one.

To check whether a given configuration is solvable or not, we have to use inversions**. A configuration is solvable if:

  • m is odd and there is an even number of inversions
  • m is even, the missing tile is on an (even|odd) row, counting from below, and the number of inversions is (odd|even).

More details here.

I didn’t manage to code anything much past this point since the sem break isn’t really long and I am tackling something I’ve never done before (this kind of problem falls into artificial intelligence, if I am not mistaken; the closest I got to this was my Sudoku Solver CS12 MP). But now, I’m picking it up again as a project to do (alongside my internship, yes). I’m solving it through this problem set (PDF). The approach is a little different from what I originally had in mind and the specification assumes that you are coding in C, but that shouldn’t be a problem. I plan to incorporate a few changes of my own as well.

Wish me luck!

Footnotes:

*n=(m^2) – 1

**Also used in analyzing the running time of insertion sort. But that’s another story.