So, after a talk on IRC with @flying_squirrel (Darcy), I decided to add a progress indicator to the program. This indicator would tell me what estimated percentage of the total number of permutations the program had exhausted and display this information in increments of 1%. As it turns out, this wasn’t very helpful. Let me explain:
Starting from the upper left hand corner (0, 0) the smallest board on which a path can be found has dimensions of 5×5. A path is found after exhausting somewhere between 1-2% of the possible permutations. As I mentioned in my previous blog entry, my computer essentially calculates this instantly.
If we increase the size of the board to 6×6, we don’t even use up 1% of the possible permutations and the result is still calculated in an imperceptibly small amount of time.
By the time we increase to 7×7, we’re still using less than 1% (I’m assuming much less) of the possible permutations, but the result takes a few fractions of a second to calculate.
At 8×8 it gets really interesting. The gauge still doesn’t register (as expected) but I let the program run for about a minute or so with no result.
This would seem to indicate that as the size of the board increases, the percentage of permutations that we need to exhaust decreases (I’m assuming exponentially) but the amount of time needed increases (also exponentially… which I kind of expected).
From this we can extrapolate that at a size of 10×10, I will probably die before the program reaches a conclusion. If there’s a better way of calculating this it’ll either involve a radical optimization of the existing program or (more likely) writing a new one from scratch.
As a matter of interest, I left the original program running in the background. We’re currently sitting at 18+ hours with (surprise) still no result.
EDIT – 13 Feb 2011:
The source code and documentation were lost. I found the source cached on Google (it’s now hosted at GitHub) and regenerated the documentation.