A Knight’s Tour Mystery on the 4x4 Board

The Curious Structure of Knight Tours on Four-Rank Boards

Medieval manuscripts on chess problems hint that some early puzzleists already sensed a hidden structure in knight’s tours on the familiar $4\times 8$ board. Several tours on that board were constructed long before the mathematics behind them was clearly understood.

By the eighteenth century, Leonhard Euler had observed two remarkable facts about tours on boards with only four ranks (four rows). First, a closed tour—one in which the knight ends one move away from its starting square—is impossible. Second, any tour that does exist must begin and end on the outer ranks of the board.

Euler stated these facts without proof. The first complete analysis appeared more than a century later, when C. Flye Sainte‑Marie presented a paper to the French Mathematical Society on April 18, 1877. Sainte-Marie not only proved Euler’s observations but also showed how the entire problem of counting tours on boards of size $4\times n$ could be reduced to a much simpler combinatorial task. In particular, he obtained the correct total of $7,772$ tours on the $4\times 8$ board (Jelliss, G.P. 2001).

A Structural Surprise

Sainte-Marie discovered that every knight’s tour on a $4\times n$ board has a remarkably rigid structure.

Theorem

On a $4\times n$ board, a closed knight’s tour is impossible. Any tour must start and finish on the outer ranks, and the path naturally breaks into two separate partial tours on two fixed groups of $2n$ squares each. These two partial tours are joined by a single move between the inner ranks.

The statement sounds mysterious, but the idea behind it is surprisingly simple.

Imagine numbering the columns of the board from $1$ to $n$. Now color certain squares Blue:

the top square of each odd-numbered column, and
the bottom square of each even-numbered column.

Call these the squares of Set A. All remaining squares form Set B.

A little inspection of the knight’s move reveals something striking: whenever the knight stands on an outer square (one of the top or bottom rows), it can move only to an inner square belonging to the same set. In other words, from the outer ranks, the knight is trapped within whichever set it started in. The only way to jump from one set to the other is by making a move entirely within the inner ranks.

Suppose a knight performs a complete tour of a $4\times n$ board. The tour visits $4n$ squares, so it consists of $4n-1$ moves. At least one of these moves must connect two inner squares; otherwise, the knight would remain forever within a single set and could never reach all squares of the board.

Now consider the outer squares. There are $2n$ of them. In a tour, every move normally connects to two squares (one entering and one leaving) except for the two endpoints of the path, which connect to only one square each.

Therefore:

$2n-2$ touter squares must be connected to two moves each.
Two outer squares (the start and finish) connect to one move each.

Counting these connections gives

.$$(2n−2)×2+2×1=4n−2$$

Thus, at least $4n-2$ moves must touch an outer square. But the entire tour contains only $4n-1$ moves. This leaves room for exactly one move that does not touch an outer square—that is, exactly one inner-to-inner move. This single move acts as a bridge between the two sets of squares. The tour, therefore, splits naturally into two separate partial tours—one within each set—linked by that lone inner jump.

Reducing the Counting Problem

Sainte-Marie’s insight leads to a powerful simplification. Instead of trying to enumerate full tours on the entire board, we need only enumerate the partial tours within one of the two sets of squares. The sets always have the same shape—an alternating pattern of “dominoes”—and one is simply the mirror image of the other across the middle of the board.

Once the partial tours of a single set are known, counting the complete tours becomes merely a matter of determining how many ways two such partial paths can be joined by the unique inner move. With this clever reduction, the formidable problem of knight tours on $4×n$ boards suddenly becomes tractable, which is a classic example of how a bit of structural insight can transform a puzzle into mathematics$^{1}$.

To test the reader's powers of deduction, a thought-provoking problem has been extracted, as usual, from the so-called Mega test. On the surface, it seems like another chess puzzle, the kind of puzzle chess players use to challenge one another. Still, it conceals the key to a new generalization that our fellow French mathematician proved in the 19th century.

The Knight's Mini-Tour

In going from square $A$ to square $B$ in the fgure, what is the maximum number of squares that a could touch, including $A$ and $B$, if the knight makes only permissible moves for a chess knight (consult a book on how to play chess if in doubt), does not touch any square more than once, and does not go outside the $16$ squares shown?

Upper bound Proof:

On the $4\times 4$ board, there are two , going from $A$ to $B$ while traversing only one set of squares (two covering the set of all blue cells and two covering the set of all yellow cells, for a real total of four) as shown below. However, since their inner ends are all on the $a$-file, or after $180°$ rotation on the $d$-file, no two can be linked by a knight move to complete a tour. Hence, no open complete tour exists under these conditions$^{2}$.

The red dots give directionality to the tour; they specify the start of the path.

On the other hand, a chessboard alternates colors, and at each move, the knight always moves from a square of one color to a square of another color. Observe that after an , the knight will find himself back on the same color as his starting square, while after an odd number of moves, he must land on a square of the opposite color. Since squares $A$ and $B$ are colored differently, the number of moves from $A$ to $B$ must be odd.

The number of moves is one less than the number of squares visited. Consequently, the number of squares visited $n\in \left\{2,4,6,8,10,12,14,16 \right\}$. Nevertheless, from the first result, it is impossible to achieve $16$, thus, a maximum of $14$ squares is what our knight can ever hope to achieve! We finally need to verify that this is indeed achievable.

Existence Proof:

Let us illustrate one such path by using for dramatic purposes. One valid path is as follows,

Each square visited is color-coded. Image generated by Matplotlib.

The knight’s tour begins as a simple chess puzzle, yet on four-rank boards it hides a surprising rigidity: two separate paths joined by a single inner leap. Once this pattern is seen, the mystery dissolves into neat combinatorics, another reminder that even the most playful puzzles can conceal elegant mathematics. You may be interested in actually seeing the combinatorics of knight's tours on $4\times n$ boards or other boards, so you are more than encouraged to explore the pages displayed on the references below, especially the one by George Jelliss, which is truly remarkable!

Notes

1. The counting of half-tours and their linking by a knight's inner move allowed Sainte-Marie to generalize open tours counting for all $4\times n$ boards.

2. It can be proved by mathematical induction that Open knight's tours exist on all $4\times n$ boards, with $n > 2$, except the $4 \times 4$. It is left as an exercise for the reader to prove this fact by employing the concepts discussed here. Note that you can find all eight half-tours that exist on a $4 \times 4$ board, and a similar argument to prove the impossibility for $n=4$.

Omni IQ Puzzles

Search This Blog