Skip navigation

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.

Leave a Reply

Your email address will not be published. Required fields are marked *