Age
14 to 18
| Article by
Toni Beardon
| Published

A Knight's Journey



What is the least number of moves needed for a knight to travel from one corner of a chessboard to the diagonally opposite corner?


You do not need to know anything about chess to understand this article and it should help you to learn about vectors. Ideas of vectors help us to solve problems about knight's moves on an extended chessboard (say a $99$ by $99$ square board).

A single knight's move takes it two squares parallel to one side of the board and one square parallel to the other side.Any such move always takes the knight to a square of the opposite colour (you might like to check this). So, as all the squares on the diagonal are the same colour, the number of moves to go to a square along the diagonal from the starting point must be even because it must take an even number of moves to get from a square of one colour to a square ofthe same colour. We first find the smallest number of moves needed to go from one corner to the opposite corner of a $99$ by $99$ square board and then solve the problem for boards of any size.

 

Image
A Knight's Journey
Label the squares: the bottom left-hand corner square as $(1,1)$, other squares across the bottom row as $(2,1)$, $(3,1)$ etc. and, in general, the square in the $x$ column across and the $y$ row up as $(x,y)$. Notice that we are labelling whole squares here and we can think of a lattice of whole number co-ordinates with points at the centres of the squares.



In this article we shall call a move from one square on the diagonal of a chess board to the next a 'diagonal step'.



Notice that to travel from corner to corner across a $99$ by $99$ board a knight has to travel $98$ diagonal steps in the direction of this diagonal.


A knight can do two types of moves...

One type of move (green arrow) has the effect of taking the knight one and a half diagonal steps forward or backwards in the direction of the diagonal (red arrow) and we denote these moves by the vectors $(2,1)$, $(-2, -1)$, $(1,2)$, and $(-1,-2)$ as shown in the diagram below. We only consider the effects of the movement in the direction of the diagonal and the perpendicular direction plays no part in this.
Image
A Knight's Journey

We should make a comment about notation here because you may meet vectors written in columns in school work, for example $\left( \begin{array}{c} 2 \\ 1 \end{array} \right)$ rather than $(2,1)$, which is just another way of writing the same thing.

The other type of move has the effect of taking the knight only half a diagonal step forward or backwards in the direction of the diagonal and we denote these moves by the vectors $(2,-1)$, $(-2, 1)$, $(1,-2)$, and $(-1,2)$ as shown in the diagram below.

Image
A Knight's Journey

Putting moves together...

We add vectors by adding the components separately, for example:

$$(2,1) + (-2,1) = (0,2)$$

$$(2,1) + (2,1) + (2,1) + (1,2) = (7,5)$$

We can take multiples of vectors (to denote a move repeated several times) by multiplying each component separately, for example repeating the move $(2,1)$ three times is given by $3$ times $(2,1)$, which we write as $3(2,1)$ or $(6,3)$. We see that

$$(2,1) + (2,1) + (2,1) + (1,2) = 3(2,1) + (1,2) = (6,3) + (1,2) = (7,5)$$

From a starting square labelled $(x,y)$ these four moves take the knight to the square

$$(x,y) + 3(2,1) + (1,2) = (x+7,y+5)$$

You can check all this vector algebra practically by counting squares on a board.

A knight can move from square $(1,1)$ to square $(99,99)$ in $66$ moves by doing the move $(1,2)$ $34$ times, the move $(2,-1)$ once, and the move $(2,1)$ $31$ times. It will finish at the square given by

$$(1,1) + 34(1,2) + (2,-1) + 31(2,1) = (99,99)$$

Smallest number of moves...

To show that it is impossible to do this in fewer moves we note that the knight has to move altogether at least $98$ diagonal steps in the direction of the diagonal from the starting to the finishing point. It might 'backtrack' or make moves taking it $1/2$ or $3/2$ diagonal steps in this direction.


As the knight can't move more than $\frac{3}{2}$ diagonal steps along the diagonal in any one move, it can't move more than $\frac{3m}{2}$ diagonal steps in $m$ moves. From this we get $\frac{3m}{2} \geq 98$ which means that $m \geq \frac{196}{3}$.

Of course $m$ is a whole number so this tells us that $m = 66$ gives the fewest possible moves and we have shown how this can be done.

Check that the moves described for the $99$ by $99$ board will not take the knight off the edge of the board at any stage and in general this is not a problem because the moves can be taken in any order.

Let us now consider the problem for an $n$ by $n$ square board. As before the knight has to move $(n-1)$ diagonal steps in the direction of the diagonal and it can't move more than $\frac{3}{2}$ diagonal steps in this direction in any one move so it can't move more than $\frac{3m}{2}$ diagonal steps in $m$ moves. From this we get the inequality $\frac{3m}{2}\geq (n -1)$.

The knight has to make slightly different combinations of moves according to whether or not $n$ is divisible by $3$ so we consider all the possibilities.

Case 1: $n = 3k + 1$

The knight makes the move $(1,2)$ exactly $k$ times then the move $(2,1)$ exactly $k$ times. This is a total of $2k$ separate moves and it takes the knight to the end position given by:

$$(1,1) +k (1,2) +k (2,1) = (1,1) + (k, 2k) + (2k,k) = (3k+1,3k+1)=(n,n)$$

The reader can check this for $n = 4, n=7$ etc. To show that it can't be done in fewer moves we use the inequality $\frac{3m}{2}\geq(n-1)$ and substitute $n = 3k + 1$ to get:

$3m \geq 2(n - 1) = 6k$

and, dividing this by $3$, we get $m\geq 2k$ and so $m = 2k$ is the smallest number of moves.

Case 2: $n = 3k + 2$

The knight makes the move $(1,2)$ exactly $k$ times, then the move $(2,-1)$ once followed by the move $(-1,2)$ once, and finally the move $(2,1)$ exactly $k$ times. This is a total of $2k+2$ separate moves and it takes the knight to the end position given by:

\begin{eqnarray}(1,1) +k(1,2) + (2,-1) + (-1,2) +k(2,1)&=& (1,1) + (k, 2k) + (2,-1) + (-1,2) + (2k,k)\\ &=& (3k+2, 3k+2) \\&=& (n,n) \end{eqnarray}

The reader can check this for $n = 5, n=8$ etc. To show that it can't be done in fewer moves we use the inequality $\frac{3m}{2}\geq(n-1)$ and substitute $n = 3k + 2$ to get:

$3m \geq 2(n - 1) = 6k + 2 $

and, dividing this by $3$, we get $m \geq 2k + \frac{2}{3}$. We know that m is a whole number so it has to be at least $2k +1$ but, in addition to this, we know that m is an even number because the starting and finishing squares are the same colour, so m is at least $2k +2$.

Case 3: $n = 3k$

When $k=1$...

Image
A Knight's Journey
It takes four knight's moves to cross to the opposite corner of a $3$ by $3$ board and this can be done as shown in the diagram below



 



When $k$ is greater than $1$...

The knight makes

  • the move $(1,2)$ altogether $k+1$ times, adding up to the vector $((k+1),(2k+2))$,
  • then the move $(2,-1)$ once,
  • finally the move $(2,1)$ exactly $k-2$ times, adding up to the vector $((2k-4),(k-2))$.
This is a total of $2k$ separate moves and it takes the knight to the end position given by:


$$(1,1) + ((k+1),(2k+2)) + (2,-1) + ((2k-4),(k-2)) = (3k,3k) = (n,n)$$


To show that it can't be done in fewer moves we use the inequality $\frac{3m}{2} \geq (n-1)$ and substitute $n = 3k$ to get:

$$3m \geq 2(n- 1) = 2(3k - 1) = 6k -2$$

and, dividing this by $3$, we get

$$m \geq 2k - \frac{2}{3} $$.

As $m$ is a whole number this means that $m \geq 2k$ and so $ m = 2k$ is the smallest number of moves.