Saturday, October 16, 2010

8-puzzle in javascript

If you're just interested in the game, this is it.

Here is the longer story...

I often heard that javascript is not a toy language anymore, its object oriented in a better way than java, its dynamically typed, supports closures etc and google does wonders with just html and javascript(e.g. the google pacman game).That feature list, and that its one of the mainstream languages in the software industry with those features, was enough for me to get excited about it. So, for a long time, I have wanted to try it out.

Last weekend, I set out to build the 8-puzzle game with html and javascript with a A* search based solver. I started by following the 4 lecture series by douglas crockford(the javascript evangelist in Yahoo). Having had some experience with scheme, it helped me to understand the philosophy behind the way things are done in javascript. Well, those 4 lectures were enough for me to get started and here I present the 8-puzzle game.

Implementation of the A* based solver is fairly well understood thing already. I used Manhattan disance heuristic. After writing the solver I realized that for some randomly generated configurations of the 8-puzzle, it was running endlessly. Thankfully, today there are debuggers, profilers and REPLs available for javascript(Firebug alone gives you all that and much more) so I could analyze my code pretty easily.
And, in the end realized that not all the randomly generated instances of 8-puzzle are solvable(for those configurations my solver was just busy searching the whole state space reachable and hence was so busy). This page describes it well and gives you enough hint on how to write a function to quickly check if an instance of 8-puzzle is solvable or not(in the given link search for "if you take a state, physically lift two consecutive tiles in that state and swap their positions, then the new state will be disconnected from old state.")

No comments:

Post a Comment