kinights tour 3

The Knight’s Tour is a mathematical puzzle that has endured over 1000 years.  The question is simple enough – a knight (which can move as illustrated above) wants to visit all the squares on a chess board only once.  What paths can it take?  You can vary the problem by requiring that the knight starts and finishes on the same square (a closed tour) and change the dimensions of the board.

The first recorded solution (as explained in this excellent pdf exploration of the Knight’s Tour by Ben Hill and Kevin Tostado) is shown below:

knights tour 4

The numbers refer to the sequence of moves that the knight takes.  So, in this case the knight will start in the top right hand corner (01), before hopping to number 02.  Following the numbers around produces the pattern on the right.  This particular knight’s tour is closed as it starts and finishes at the same square and incredibly can be dated back to the chess enthusiast al-Adli ar-Rumi circa 840 AD.

Despite this puzzle being well over 1000 years old, and despite modern computational power it is still unknown as to how many distinct knight’s tours there are for an 8×8 chess board.  The number of distinct paths are as follows:

1×1 grid: 1,
2×2 grid: 0,
3×3 grid: 0,
4×4 grid: 0,
5×5 grid: 1728,
6×6 grid: 6,637,920,
7×7 grid: 165,575,218,320
8×8 grid: unknown

We can see just how rapidly this sequence grows by going from 6×6 to 7×7 – so the answer for the 8×8 grid must be huge.  Below is one of the 1728 solutions to the 5×5 knight’s tour:

knights tour 5x5

You might be wondering if this has any applications beyond being a diverting puzzle, well Euler – one of the world’s true great mathematicians – used knight’s tours in his study of graph theory.  Graph theory is an entire branch of mathematics which models connections between objects.

Knight’s tours have also been used for cryptography:

kinights tour 2

This code is from the 1870s and exploits the huge number of possible knight’s tours for an 8×8 chess board.  You would require that the recipient of your code knew the tour solution (bottom left) in advance.  With this solution key you can read the words in order – first by finding where 1 is in the puzzle (row 6 column 3) – and seeing that this equates to the word “the”.  Next we see that 2 equates to “man” and so on.  Without the solution key you would be faced with an unimaginably large number of possible combinations – making cracking the code virtually impossible.

If you are interested in looking at some more of the maths behind the knight’s tour problem then the paper by Ben Hill and Kevin Tostado referenced above go into some more details.  In particular we have the following rules:

An m x n chessboard with m less than or equal to n has a knight’s tour unless one or more of these three conditions hold:

1) m and n are both odd
2) m = 1, 2 or 4
3) m = 3 and n = 4,6,8

Investigate why this is!

If you enjoyed this post you might also like:

e’s are good – He’s Leonard Euler. A discussion about the amazing number e and Euler’s use of graph theory.

Sierpinski Triangles and Spirolateral Investigation Lesson Plan. A lesson to introduce the mathematics in art and fractals.