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.

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.

## One Trackback/Pingback

[…] 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 […]