The knight's perfect tour, challenge chess with linear optimization

Challenge solution

A valid closed tour on the $8 \times 8$ board is given by the following continuous sequence of $64$ moves:

In total, there are more than 33 trillion tours, of which around 26 trillion allow returning to the initial square.

To solve the Knight’s Tour systematically, we can use an integer linear optimization model based on the Miller-Tucker-Zemlin subtour elimination formulation (Miller et al., 1960).

Index sets

• \(\mathcal{V} = \{1, 2, \dots, N\}\): Set of $N = n^2$ board squares ($N = 64$ for an $8 \times 8$ board).
• \(\mathcal{A} \subset \mathcal{V} \times \mathcal{V}\): Set of directed arcs $(i,j)$ representing valid knight moves between square $i$ and square $j$.

Parameters

• \(N\): Total number of board squares ($N = 64$).

Decision variables

• \(x_{ij} = 1\) if the knight moves directly from square $i \in \mathcal{V}$ to square $j \in \mathcal{V}$, and $0$ otherwise.
• \(u_i \in \{1, \dots, N\}\): Continuous auxiliary variable indicating the visiting order of square $i \in \mathcal{V}$ in the tour sequence.

Since this is a feasibility problem (finding a Hamiltonian cycle in the knight’s movement graph), the objective function is arbitrary:

Objective function

\[\min z = 0\]

We now define the model constraints:

Exactly one outgoing move per square:

\[\displaystyle \sum_{j : (i,j) \in \mathcal{A}} x_{ij} = 1 \quad \forall i \in \mathcal{V}\]

Exactly one incoming move per square:

\[\displaystyle \sum_{i : (i,j) \in \mathcal{A}} x_{ij} = 1 \quad \forall j \in \mathcal{V}\]

Subtour elimination (MTZ Formulation):

\[u_i - u_j + N x_{ij} \leqslant N - 1 \quad \forall (i,j) \in \mathcal{A}, \; i \neq 1, \; j \neq 1\]

Variable domains:

\[u_1 = 1\] \[1 \leqslant u_i \leqslant N \quad \forall i \in \mathcal{V}\] \[x_{ij} \in \{0,1\} \quad \forall (i,j) \in \mathcal{A}\]

Source code

The Python implementation of the optimization model presented in this post is available in the GitHub repository.

GitHub Repository: fjmartincampo/KnightsTour