Non-intersecting chessboard paths

This Riddler classic puzzle is about finding non-intersecting paths on a chessboard:

First, how long is the longest path a knight can travel on a standard 8-by-8 board without letting the path intersect itself?

Second, there are unorthodox chess pieces that don’t exist in the standard game, which are known as fairy chess pieces. What are the longest nonintersecting paths that can be taken by the camel (which moves like a knight, except 3 squares by 1 square), the zebra (3 by 2), and the giraffe (4 by 1)?

This is a very challenging problem, and there doesn’t appear to be any way to solve it via some clever observation or simplification. Of course, we can try to come up with ever longer tours by hand, but we’ll never know for sure that we have found the longest one.

Much like the recent Pokemon Go problem, we must resort to computational means to obtain a solution. In this case, however, the problem is “small enough” that we can find exact solutions!

Here are some optimal tours:
[Show Solution]

If you’re interested in the details of how I found my solutions, read on:
[Show Solution]

7 thoughts on “Non-intersecting chessboard paths”

  1. I was able to get your code ported into Matlab using intlinprog (I know a few other languages, but Matlab is the one I’ve been using most for the last few months, so I took the lazy route). It took 2 hours total for the knight, but it works. Thank you for teaching me a new tool for my toolbox!

    1. Neat — there can be a lot of variability in solve time based on which solver you use. It’s not necessarily Matlab’s fault mind you. Since the B and C matrices are sparse, have you tried declaring them as sparse matrices in Matlab? If the intlinprog solver can take advantage of sparsity this would make a big difference.

      1. Yeah, I used sparse matrices. I think I’m getting nearly the same run-time as you, about 10-15 minutes for each solution, but it gave me 10 different subtour solutions before giving the final answer. I could really speed things up with symmetry, since the first four solutions are just the same subtours rotated or mirrored.

        I got myself an academic license for Gurobi, and it sped things up a bit, but I think it would be way faster if I implemented it in Python with a lazy constraint callback to eliminate subtours as it solves.

Leave a Reply to Bob Long Cancel reply

Your email address will not be published. Required fields are marked *