List Comprehension

I am enrolled in an Artificial Intelligence class this quarter which consumes about 20 hours per weekend every other weekend for the fortnightly programming assignment. (This is just how long it takes to complete the programming assignments, and doesn't include time spent preparing for the weekly quizzes, doing the required reading, completing the regular homework assignments, and studying for tests. Not that I'm complaining. I signed up for this, after all. :)) The programming part isn't usually too bad -- maybe eight hours of work -- but then I have to write a paper about the assignment. The writing usually takes quite a bit longer. Anyway, this is one of those weekends, but I'm taking a short break to talk about my current assignment and this sweet use of list comprehension I just whipped up.

We are studying constraint satisfaction problems and our latest assignment is to solve the game of Sudoku using some specific heuristics. We can use any programming language we choose, so I have used Python for all of the assignments so far. Python is so awesome that sometimes I feel like I'm cheating. For example, for this assignment, in order to implement one of the heuristics, I had to get a list of the coordinates for each block in the puzzle.

The "board" is basically a 2-dimensional array, where the top-left cell is at (0, 0) and the bottom-right cell is at (8, 8). Recall that the board is broken into 9 blocks of 9 cells each. The first block consists of the first 3 cells in each of the first 3 columns. What I was trying to get was a list of the coordinates for each cell in each of the blocks. The first block would look like this:

[(0, 0), (0, 1), (0, 2),
 (1, 0), (1, 1), (1, 2),
 (2, 0), (2, 1), (2, 2)]

The standard way to do this kind of thing, and the approach I would have taken if I were writing this in Java or C++, is to put together a couple of for loops and iteratively populate a big array. The whole thing might take 3-5 lines of code. But in Python, we can take advantage of some really cool features, like list comprehension, that can save the programmer a lot of time.

So here it is, the coordinates of each block in a Sudoku puzzle, in one line of Python:

>>> x = [[(i + a * 3, j + b * 3) for i in range(3) \
for j in range(3)] for a in range(3) \
for b in range(3)]
>>> x
[[(0, 0), (0, 1), (0, 2),
 (1, 0), (1, 1), (1, 2),
 (2, 0), (2, 1), (2, 2)],
[(0, 3), (0, 4), (0, 5),
 (1, 3), (1, 4), (1, 5),
 (2, 3), (2, 4), (2, 5)],
[(0, 6), (0, 7), (0, 8),
 (1, 6), (1, 7), (1, 8),
 (2, 6), (2, 7), (2, 8)],
[(3, 0), (3, 1), (3, 2),
 (4, 0), (4, 1), (4, 2),
 (5, 0), (5, 1), (5, 2)],
[(3, 3), (3, 4), (3, 5),
 (4, 3), (4, 4), (4, 5),
 (5, 3), (5, 4), (5, 5)],
[(3, 6), (3, 7), (3, 8),
 (4, 6), (4, 7), (4, 8),
 (5, 6), (5, 7), (5, 8)],
[(6, 0), (6, 1), (6, 2),
 (7, 0), (7, 1), (7, 2),
 (8, 0), (8, 1), (8, 2)],
[(6, 3), (6, 4), (6, 5),
 (7, 3), (7, 4), (7, 5),
 (8, 3), (8, 4), (8, 5)],
[(6, 6), (6, 7), (6, 8),
 (7, 6), (7, 7), (7, 8),
 (8, 6), (8, 7), (8, 8)]]
>>> len(x)
9
>>> x[0]
[(0, 0), (0, 1), (0, 2),
 (1, 0), (1, 1), (1, 2),
 (2, 0), (2, 1), (2, 2)]
>>> x[1]
[(0, 3), (0, 4), (0, 5),
 (1, 3), (1, 4), (1, 5),
 (2, 3), (2, 4), (2, 5)]
>>> x[8]
[(6, 6), (6, 7), (6, 8),
 (7, 6), (7, 7), (7, 8),
 (8, 6), (8, 7), (8, 8)]