It seems I’ve made some significant progress with the algorithm, just not enough yet.
After some discussion in the comments of my last entry, I decided that my next attempt should be to add a check after every move to make sure that I hadn’t boxed any positions in, making them unreachable.
I almost dismissed this idea because I originally thought that it would involve checking every position on the board after every move, but it’s only necessary to check the eight positions that can be moved to from the current one.
The end result was this: on a 7×7 board, I can now compute the same path in 614 iterations as opposed to the 4430 required before. This represents an efficiency increase of slightly better than 720% (although that admittedly doesn’t account for the overhead added to each iteration by the check itself). An 8×8 board still takes an unknown amount of time however.
The thing that this check doesn’t take into account is the fact that there could be a cluster of positions that can reach each other, but can’t be reached from outside; as opposed to a single, isolated position. I had thought of this before I implemented the check, but hoped that it wouldn’t be a significant problem. It now seems that it may be.
It would seem that the next step is to find a way to look for clusters of isolated positions, although I haven’t yet quite decided how to go about that from a programming standpoint. Whatever I do, I’ll have to make sure that the checking process itself is as efficient as possible.
EDIT – 13 Feb 2011:
The source and documentation for this version were lost. I was able to recover the source (without doxygen comments) from Google’s cache, but I had to re-write much of the documentation. The code is now hosted at GitHub.