Non-intersecting chessboard paths

Here are optimal-length knight paths computed for various board sizes:

Of course, we aren’t restricted to square boards. It’s just as easy to compute for example a max-length knight path on a 12×4 board:

For the alternate chess pieces mentioned in the problem statement, the code only requires slight modifications; i.e. there are more ways for paths to cross when a giraffe moves vs when a knight moves. But otherwise, the structure of the optimization problem is identical. Here are some optimal-length paths for the four different pieces:

For the camel path, we can take advantage of the fact that the camel always remains on squares of the same color, so we are effectively solving the problem on a board with half as many squares! As we can see, there are no patterns in the solutions; this is truly a difficult problem and without powerful computational tools, we would be hard pressed to find these solutions by hand. In the next section, I go into detail about how I solved the problem and I also include my code if you’re interested in solving it yourself!

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:

1. Solve the problem as-is
2. See if the solution has any subtours. If not, we’re done!
3. 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.
4. 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.