The Knight’s Path Puzzle

Reductio ad absurdum is one of a mathematician’s finest weapons. It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but the mathematician offers the game. — G. H. Hardy, 1877–1947

Chessboards provide a rich setting for mathematical puzzles. Even a small board can conceal problems involving counting, arrangements, and ingenious restrictions on movement. Consider the following challenge, taken from Ronald Hoeflin’s Mega Test. A knight must travel from square AA to square BB on a 4×44\times4 chessboard, following its usual L-shaped movement. It cannot visit any square more than once or leave the board. What is the maximum number of squares it can visit, including its starting and ending squares? 1

4x4chessboard
Figure 1. AI-stylized image

Hints

Reveal Hint 1

What happens to the color of a square every time a knight moves?

Reveal Hint 2

What happens to the board if you temporarily remove its four central squares?

Solution

Reveal solution

A Chessboard of Two Colors

empty4x4

A chessboard alternates colors, and each move takes the knight from a square of one color to a square of the other. After an even number of moves, the knight will be back on a square of the same color as its starting square; after an odd number of moves, it must land on a square of the opposite color.

Since squares AA and BB are colored differently, the knight must make an odd number of moves. The number of moves is one less than the number of squares visited. Consequently, the number of squares visited n∈{2,4,6,8,10,12,14,16}  n\in \left\{2,4,6,8,10,12,14,16 \right\}.2

The Four Central Squares: An Impossible Journey

4x4chess

Suppose for a moment that we were to remove the four central squares of our mini chessboard; that is, we remove the set

S={b2,c2,b3,c3}S=\{b2,c2,b3,c3\}

What remains is divided into six groups, according to which squares can be reached from one another using knight moves without passing through a central square. Here is the complete arrangement:

4x4chesspuzzle

The six groups are:

GroupSquares
1a1a1
2d1d1
3a4a4
4d4d4
5b4,d3,c1,a2b4,d3,c1,a2
6c4,a3,b1,d2c4,a3,b1,d2

The first four groups consist of isolated corner squares: their only possible knight moves lead to one of the four central squares. The last two groups each form a cycle:

b4→d3→c1→a2→b4,b4\to d3\to c1\to a2\to b4,

and

c4→a3→b1→d2→c4.c4\to a3\to b1\to d2\to c4.

The crucial observation is that there are no legal knight moves between two different groups unless the knight lands on one of the four removed central squares.

What happens if we try to visit all sixteen squares?

Suppose, for the sake of contradiction, that a knight can visit all sixteen squares exactly once. We can represent its route as an ordered sequence:

v1→v2→v3→⋯→v16.v_1\to v_2\to v_3\to\cdots\to v_{16}.

Every square appears exactly once in this sequence. Now remove the four central squares from the sequence. What happens? The remaining twelve squares are divided into separate stretches. For example, a hypothetical sequence might look like

v1,v2⏟first stretch,v3,v4,v5,v6⏟second stretch,v7,v8,v9⏟third stretch,\underbrace{v_1,v_2}_{\text{first stretch}}, \quad v_3, \quad \underbrace{v_4,v_5,v_6}_{\text{second stretch}}, \quad v_7, \quad \underbrace{v_8,v_9}_{\text{third stretch}},

where v3v_3 and v7 v_7 represent removed central squares. With four removed squares, the greatest possible number of stretches is five. This is simply because:

  • Initially, we have one uninterrupted sequence.
  • Removing the first square can split it into at most two stretches.
  • Removing a second square can increase the number to at most three.
  • Removing a third can increase it to at most four.
  • Removing a fourth can increase it to at most five.

In general, removing kk elements from a sequence can create at most k+1k+1 nonempty stretches or sections3. Therefore, our hypothetical route can produce at most five stretches after the four central squares are removed. However, we need at least six stretches. Remember that the remaining twelve squares belong to six separate groups.

Since there are no knight moves connecting different groups, the knight cannot move directly from one group to another without passing through a central square. But we have removed the central squares from our sequence. Hence, each uninterrupted stretch must consist entirely of squares belonging to the same group. And because the knight must visit every remaining square, it must visit all six groups. Therefore, we need at least six separate stretches: one for each group.

We have reached a contradiction:

6⏟minimum stretches required>5⏟maximum stretches possible. \underbrace{6}_{\text{minimum stretches required}} > \underbrace{5}_{\text{maximum stretches possible}}.

Thus, the knight cannot visit all 1616 squares exactly once, and a maximum of 14 14 squares is what our knight can ever hope to achieve! We finally need to verify that this is indeed achievable.

One valid path is as follows,

knight
 Each square visited is color-coded. AI-generated image via Matplotlib.

Another knight Puzzle: Non-attacking knights

What is the maximum number of knights that can be placed on a 4×44\times4 chessboard without any two attacking one another?

Solution

Reveal solution
4x4chess

The answer is eight. Place a knight on every square of one color. Since knights always move to squares of the opposite color, none of these knights attacks another. Partition the sixteen squares into eight pairs, with the two squares in each pair separated by a legal knight’s move. For instance:

(a1,b3),(c1,d3),(a2,b4),(c2,d4),(a3,b1),(c3,d1),(a4,b2),(c4,d2).\begin{aligned} &(a1,b3),\quad(c1,d3),\\ &(a2,b4),\quad(c2,d4),\\ &(a3,b1),\quad(c3,d1),\\ &(a4,b2),\quad(c4,d2). \end{aligned}

Since no two knights can occupy the same pair, there can be at most eight knights. Therefore,

Nmax⁡=8. \boxed{N_{\max}=8}.

What about an 8×88\times8 board? What is the maximum number of non-attacking knights that can be placed on it?

Beyond Knights

The knight’s journey is only the beginning. A chessboard holds far more mathematical surprises than its sixty-four squares might suggest. How many ways can pieces be arranged without threatening one another? What hidden patterns emerge when squares are removed or covered? And what seemingly impossible configurations can be ruled out with nothing more than a clever observation?

The puzzles below offer a taste of these fascinating challenges. Don’t be surprised if some of them leave you scratching your head! We will return to each in future installments of Combinatorics on the Chessboard, where we will uncover their solutions and the beautiful mathematical ideas behind them. In the meantime, why not try your hand at one?

The Four Queens Puzzle

Can four queens be placed on a 4×44\times4 board so that none attacks another? What about an 8×8 8\times8 board? What is the maximum number of non-attacking queens that can be placed on a standard chessboard? How many distinct arrangements exist?

A focused view of a black queen chess piece with blurred chessboard background.

The Mutilated Chessboard

If two opposite corners are removed from a regular chessboard, can the remaining squares be covered by dominoes, each occupying two adjacent squares?

Mutilated Chessboard Vectorized.svg?utm Source=en.wikipedia

The Non-Attacking Rooks Problem

How many rooks can be placed on a board without attacking one another? How many different arrangements are possible?

Frosted glass chess rook set on a chessboard against a dark background.

Notes & References

Technical Notes & References
  1.  Adapted from Hoeflin, R. K. (1985, April). Problem 29 in The Mega Test. Omni, 7(4), p. 129.  ↩︎
  2. A note on mathematical invariants. An invariant is a property or quantity that remains unchanged under a set of allowed operations. In this example, the knight changes the color of its square with every move. However, the relationship between the square’s color and the parity of the number of moves remains constant: after an even number of moves, the knight is on a square of its starting color; after an odd number, it is on the opposite color. This is an example of invariant-based reasoning, a useful technique in combinatorial problems. ↩︎
  3. If removing kk elements from a sequence can produce at most k+1k+1 uninterrupted sections, but the remaining elements must occupy at least k+2k+2 separate sections, the original sequence cannot exist. ↩︎

Leave a Comment

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