04 April 2011

Knight's Path algorithm, pt. 2

Last post I promised you a keyword: optimize.

What is the optimal size board for the random knight's path algorithm (see previous post)? Turns out this question does not have a very interesting results. The 3x3 board is the most efficient of the non-trivial cases, and efficiency decreases as the board expands. Moving on... 

My original interest was in random movements, but I wasn't done there. I wanted longer path lengths and so needed to let the algorithm make a few decisions along the way.  

Thus, instead of allowing completely random moves, we can forbid jumping to one's death. That is, if there is more than one legal move to make, we forbid jumping to a dead-end square. This slight modification improves performance on the 8x8 board; the average path length increases about 25%. 

I changed the algorithm again to pick the move with the fewest next-jump options (while still forbidding death jumps). Essentially, the algorithm looks around to see where the knight can jump, then counts how many next-jump options there are from each of those positions, and picks the one with the fewest. In this way, the algorithm intentionally visits isolated squares when it has the chance. With this modification, the algorithm produces a complete path (path length = 64) over 98% of the time with closed paths comprising 14% of complete paths. (A closed path is a complete path where the final position is within one jump of the starting position, meaning the circuit can be closed.) Here is a demonstration of one such complete, closed path:

Notice that any position on the board could be the starting position since the path loops around. Also, complete, closed paths often display rather beautiful patterns that could, you know, inspire somebody.

I purposely avoided reading the literature on the problem before working on it; achieving one’s own results is worthwhile in recreational mathematics. However, a quick search shows that H.C. von Warnsdorff proposed the same automated process -- picking the move with the fewest next-jump options -- in 1823. (He was not using a computer.)

Read more about knight's paths on Wolfram MathWorld, one of my favorite websites. 

No comments:

Post a Comment