Skip navigation

Tag Archives: python

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.

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.