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.

Essential resources for IB students:

1) Revision Village

Screen Shot 2021-05-19 at 9.55.51 AM

Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams.  I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.

Screen Shot 2018-03-19 at 4.42.05 PM.png

There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions.  What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial.  Really useful!

Screen Shot 2021-05-19 at 10.05.18 AM

The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers.   These all have worked solutions and allow you to focus on specific topics or start general revision.  This also has some excellent challenging questions for those students aiming for 6s and 7s.

Each course also has a dedicated video tutorial section which provides 5-15 minute tutorial videos on every single syllabus part – handily sorted into topic categories.

2) Exploration Guides and Paper 3 Resources

Screen Shot 2021-05-19 at 6.32.13 PM

I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations.  The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.