{kode.play();}

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.