It seems that I’m done coding the A* search of my n-puzzle solver. I spent almost all of last week doing it, as I discovered that there are some flaws in my understanding of A*.
The web doesn’t seem to have a lot of resources on A* compare to, say, graph algorithms. Google “a* search” and the only relevant link you’ll get is the first hit, a Wikipedia article at that. The second search hit, remarkably funny (for me, at least), is a search engine for cemetery records. The best search terms seem to be either “a* search algorithm” or “a* searching algorithm“. And even at that, not all the hits in page one have something to do with A*. Compare with, say, googling for “bellman ford” to find resources on the Bellman Ford algorithm. The best A* resource for beginner’s that I found on the the web will be this.
I said that my A* seems to work because I haven’t managed to make it solve randomly generated solvable instances yet; solving time takes too long that my computer heats up so much to the point of auto shut down. I’ve managed to get it to solve an instance with a Manhattan distance of 11 but I haven’t tried anything further than that yet (the randomly generated instances of size n=15 usually take a Manhattan distance of around 30, give or take).
I wonder how things would’ve went if I implemented my search in Java instead of Python. I remember, when I ran a (hopelessly inefficient) Java brute-force Sudoku solver in my old HP Pavilion DV1000 (default specs, i.e., Windows XP Home Edition, 1.5GHz processor, 512MB RAM), I managed to keep it up for hours, though, to make things fair, I did that in an air-conditioned room. For comparison, I ran my A* on a Gateway T-series (can’t give exact model as it is not available on surface inspection, sorry), running Ubuntu 10.04 (Lucid Lynx) with AMD Turion 64 X2 (approx 2GHz) processor and 2GB RAM, room temperature.
Maybe, I’ll look into Iterative Deepening A* next with some time.sleep lines thrown in the code to allow time for my system to cool down. Stay tuned.