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:
- Generate a random instance of the puzzle.
- 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:
- Generate the solved instance of the problem.
- 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.