Solving the Princess in a Box Puzzle

We can solve the puzzle of my last post using a Breadth-first search (BFS) algorithm. The key idea is to realize than the problem is just a Shortest Path problem where the graph, even when it is not completely known at the beginning (because we don't have the graph's adjacency list or adjacency matrix), can be built joining the states the board takes after every movement. The image below can help to understand this. It shows some of the states the board cab take after some movements starting from the beginning.

So we are going to work over the graph of all the states the board can take by moving the pieces around. A nice thing is that the BFS algorithm assures us that if we reach our target we would reach it in the minimum number of steps, and if we can't reach our target the problem is indeed impossible to solve. BFS in seudocode looks like this:

But we'll need to modify some parts of this algorithm in order to solve our problem. See the highlighted lines below:

Lines 1-4 are no longer necessary (or possible) because we don't have the adjacency list or adjacency matrix. We don't even know the number of nodes our graph has!. Line 5 need to change because the above restriction forces us to attach the State property into our node, the same applies to lines 12-16. Line 11 and 18 would be ignored here because we don't need any special process after discovering a graph edge, there are other interesting problems with graphs that can be solved using these steps but not our problem at hand. So our algorithm ends like this:

In line 4 we have introduced a Discovered data structure, this object stores all the discovered nodes and can be a Set or Hash Table because we need to insert nodes and check their existence fast. This change is required because we don't know all the nodes at the beginning so we can't use a simple Array. As always everything is easy until you have to do it, and here the simple and innocent line 10 can give us a bit of trouble implementing it, but after a bit of code modifications we'll end with this:

This can solve the puzzle in less than 3 seconds (in my desktop with Windows7 and a Pentium D at 2.8 GHz) pretty nice if we are talking about Flash here, I have seen some native applications taking similar or longer times.
But some optimizations were required to obtain that speed. Also in order to don't freeze the browser I had to split the process along some frames, but that was easy because in a BFS process there is no recursion involved. It's a shame than Flash still doesn't have threading support despite the fact that HTML5 already got web workers.