Knight’s Tours: Worlds Oldest Math Challenge

Over the last two weeks, we have studied the content of water and water used by the human body and by humans in the products that we manufacture. We were then discussing the water cycle where the sun’s warmth turns liquid water into gas (clouds) in the form of evaporation, then water vapor in the air cools down and turns back into liquid water in the form of condensation, and through precipitation, water falls from the clouds as rain and snow, to collect in the oceans, rivers, lakes, and streams and infiltrate into the ground for us to drink.

Then I thought, what would be a great mathematical challenge having to do with a cycle or circuit. When I was a child, I turned my passion for chess into many games. I would play with various chess pieces and move them around the chess board and see if I could fill every space. After completing my first circuit with a knight, I thought I had discovered something original. After a little research, I found that this challenge was called a Knight’s Tour and has been studied by mathematicians since at least 840AD. Oh well, not original but still a lot of fun. How does a Knight’s Tour work?

A knight is placed on any square ("cell") on a rectangular grid and moved until all cells are covered.

A knight cannot visit the same square twice; number each move from 1-64.

You can start from any one of the 64 squares on the chess board.   

The knight moves in an "L" pattern; two squares horizontally or vertically; then one square to the right or left; knights may jump over other moves.

If the 64th cell is one knight's move from the 1st cell, it is a Closed Knight's Tour.

The earliest recorded example of a Knight's Tour is described in an arabic manu-script with the title "Nuzhat al-arbab   al-aqulfi'sh-shatranj al-manqul" (The delight of the intelligent, a description of chess) and came from al-Adli-ar-Rumi.

al-Adii-ar-Rumi was a professional chess player who lived in Bagdad in 840 A.D.  

The pattern of a Knight's Tour was presented in verse form in the highly stylized Sanskrit poem Kashmiri poet Rudrata.

I tried to solve a Knight’s Tour in class with the children and they saw my strategy of focusing on the perimeter moving in a clockwise or counterclockwise fashion or both. They also were able to see what happens when you think you are stuck (can’t make another knight’s move to an empty cell). Using the method of recursion, you can erase your last few numbers and move in a different direction until you maximize your solution. When you reach your maximum solution, circle that number. 

After solving a knight’s tour or a high number solution, you can check your moves by drawing lines from the middle of each cell in order of the numbers uncovering a beautiful design. If you made a mistake in one of the moves, it is not a knight’s tour but you can learn from your mistake.

I recommend trying this challenge with your friends and family to see how many different solutions you can generate.

Before starting this lesson on Knight's Tours, I challenged the students to think of what are the fewest lines I could draw to create an enclosed 8x8 grid. Most children impulsively say 16 adding 8 + 8. I then ask them to think of a 3x3 grid and they quickly see that the solution is 4 + 4 = 8 for the 3x3 grid. Then I asked them to apply that to building an 8x8 grid and they see 9 + 9 = 18. Then we built an algebraic expression for an n x n grid: 2n + 2. Then I can ask them how many lines to build a 100 x 100 grid and they quickly see 202. "Seeing" algebraic expressions to solve complex problems is a great tool to develop.