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]
Even though we’re resorting to a numerical solution, we must still be careful about how we proceed. There is an astronomical number of possible paths on a chessboard, so simply enumerating and checking each path is out of the question! Instead, we’ll think about the problem as a visiting nodes on a graph. Here, each node is a cell and edges connect pairs of cells between which a knight can move.
Let’s define the following matrices:
- Adjacency matrix: Suppose there are $N$ total cells and we enumerate them $1,2,\dots,N$. $A \in \{0,1\}^{N\times N}$ encodes which cells are reachable from which other cells. $A_{ij} = 1$ if you can move from cell $i$ to cell $j$.
- Incidence matrix: Suppose there are $M$ total edges (nonzero entries in $A$) and we enumerate them $1,2,\dots,M$. $B \in \{0,1\}^{N\times M}$ encodes which cells are connected by each edge. $B_{ij} = 1$ if edge $j$ involves cell $i$.
- Conflict matrix: The matrix $C\in\{0,1\}^{M\times M}$ indicates which edges cross. $C_{ij} = 1$ if edges $i$ and $j$, excluding the case where the edges share one cell in common.
It’s a bit tedious to figure out what $A$, $B$, and $C$ are, but it’s relatively straightforward to do in code by looping through all nodes or edges as necessary. We now define the following variables for our optimization model:
\begin{align*}
x_1,\dots,x_M &: \text{ variables indicating which edges are used} \\
z_1,\dots,z_N &: \text{ variables indicating which cells are used} \\
w_1,\dots,w_N &: \text{ variables indicating endpoint cells}
\end{align*}We then have three main constraints:
\begin{align*}
\sum_{i=1}^N w_i &\le 2 & & \text{(we have at most two endpoints)}\\
B x &= 2z-w & & \text{(two edges per cell, one per endpoint)}\\
C x &\le H(1-x) & & \text{(no self-intersecting paths)}
\end{align*}
In the last constraint, $H$ is a constant that upper-bounds the number of paths that can intersect any given path. Generally, we can set $H$ to be equal to the maximum row sum of $C$. In the case of a knight tour, $H = 9$. This is an example of the M-trick in integer programming.
Of course, our goal here is to maximize $\sum_{i=1}^M x_i$, the total length of the path. As formulated, this is an integer program that is a version of the Traveling Salesman Problem (TSP) with additional constraints. Unfortunately, the formulation above doesn’t always give a valid solution, since it doesn’t explicitly forbid disjoint paths, e.g. paths with separate closed loops. These are known as subtours.
To get rid of subtours, I used a standard heuristic:
- Solve the problem as-is
- See if the solution has any subtours. If not, we’re done!
- If $\{x_{k_1},\dots,x_{k_\ell}\}$ is a subtour, add the constraint: $\sum_{i=1}^\ell x_{k_i} \le \ell-1$ to explicitly forbid this subtour from occurring in the solution.
- Re-solve the problem and return to step 2.
This heuristic always eventually yields an optimal solution, but it may take awhile. For this problem, I only had to re-solve about 10 times before finding a subtour-free (and hence optimal) path.
I used IJulia, JuMP, and Gurobi to solve the integer programs, and on my laptop it took about 30 seconds for 6×6, 1 minute for 7×7 and 5-10 minutes for 8×8. These times only account for a single solve. Subtour eliminations required up to 10 solves per case to find an optimal path.
If you’re interested in seeing my code in full detail, you can view/download my notebook here.
I should also point out that this is a well-studied problem. Some references include: the encyclopedia of integer sequences, non-crossing knight tours, and non-intersecting paths.
Caught a typo: “Bx = 2x-w” needs to be “Bx = 2z-w”
thanks! fixed it.
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!
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.
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.