Updated date:

Chess, Rice and Knights

I have been teaching mathematics in an Australian High School since 1982, and I am a contributing author to mathematics text books.

Have you played chess? It is a two-player game of strategy using a board consisting of 64 squares and 32 pieces representing two armies. Each piece has strength-value in terms of how it moves on the board. The aim is for a player to capture the opponent’s King, known as checkmate.

Seeking mental stimulation but bereft of a human opponent, I decided to challenge the computer to a game of chess and, in a fit of hubris, I set the difficulty level to 8 out of a maximum 10. After a considerable number of definitive defeats, (oh hell, I now admit the computer figuratively pummelled me without shame!), I sheepishly rolled back the clock and started at level 1. But I am now proud to boast that my play status is a respectable level 5.

Humbled, I reflected on the origin of the game.

my-kingdom-for-a-horse

There are stories, perhaps apocryphal, concerning the genesis of the game. One popular story relates that an ancient King potentate, after vanquishing all foes, became bored and summoned his wise man to find a way of occupying the remainder of his restless days.

The wise man devoted many hours to the task and presently reported to the King.

“Great One,” he began, “here is a battle in the making where no blood will be shed. You will need a strong mind for victory and your mettle will be heavily taxed. To triumph in this battle, you must bear sacrifice and know the mind of your enemy.”

The King was intrigued. After listening attentively to the wise man’s discourse, he retreated for many days of study and play.

my-kingdom-for-a-horse

The King returned happy and summoned for the wise man to be brought before him.

“Wise one, I have spent many glorious days vanquishing all challengers, and not a drop of blood was shed. Thou art truly to be thanked. Name any reward you desire.”

The wise man bowed. “Sire, my only desire is that the game enriches your life and opens up before you the wisdom of the ages.”

“Take 100 acres of royal land to catch all the game you can eat,” the King insisted.

The wise one bowed again before speaking.

“My lord, if you insist on conferring a favour upon me, then I ask for the following.”

The King nodded in agreement and motioned for him to continue.

“There are sixty-four squares on the battlefield. Place one grain of rice on the first square, two grains on the second square, four grains on the third, eight grains on the fourth and thusly for the remaining sixty squares. I humbly ask that you present to me the total number of grains.”

my-kingdom-for-a-horse

The King was peeved that the wise man did not want to take advantage of his generosity.

“What you ask for is a pittance. But I shall have it done anon”.

He requested his minions to carry out the strange request by the following day.

“Have you carried out your order?” the King demanded.

“We could not, Sire. What you ask for is worth more than your Kingdom.”

Geometric sequence

The number of grains of rice the wise man requested follows a pattern (sequence) known as a geometric sequence.

This means each number (term) of the sequence is obtained from the previous term by multiplication or division by a constant number (the common ratio).

The wise man asked that the number of grains of rice be doubled for each square, thus generating a geometric sequence with a common ratio of 2.

my-kingdom-for-a-horse

The value of the nth term is found using

my-kingdom-for-a-horse

To find the number of rice grains on the 64th square we use a = 1, r = 2, n = 64.

my-kingdom-for-a-horse

This is approximately 1,000,000,000 times larger than the world population of 7,800,000,000, which is a staggering number of rice grains!

However, we are not finished. Remember that the King’s wise man wanted the total number of grains, not just the amount on the last square.

Sum of a geometric sequence

To find the total number of rice grains, we use another formula, which calculates the sum of a geometric series.

my-kingdom-for-a-horse

The formula is:

my-kingdom-for-a-horse

For our geometric series, we use a = 1, r = 2, n = 64, as before.

my-kingdom-for-a-horse

To put this in a different perspective, the current world production of rice is about 24,052,000,000,000,000 grains.

The wise man asked for 18,446,744,073,709,600,000 grains of rice.

This is 767 times greater than the world production!

my-kingdom-for-a-horse

Knight solitaire

Let us leave the King and his wise man for the history books and focus on what I like to call Knight solitaire.

Four pieces that are used in chess are the rook (castle), Queen, King and knight (horse). Starting in any of the sixty-four squares on an empty board, each of them can be moved to any other square. I am particularly drawn by the movement of the knight, which can move to a maximum of eight positions in an L shape.

my-kingdom-for-a-horse

This prompts the challenge:

Starting from a given square, can the knight visit every square exactly once?

Many solutions exist, each creating an interesting pattern.

my-kingdom-for-a-horse

A trial-and-error approach can be used, but this can lead to being trapped, sometimes on the second last square.

Intuitively, you might suspect that starting on the edge and filling squares inwards in a circular way is sensible, since the outer spaces might be hard to get to later. Alternatively, it also makes sense to start near the middle and radiate outwards, again moving in a circular fashion.

my-kingdom-for-a-horse

The reality is that both methods -and others- can work if they satisfy Warnsdorff’s algorithm. This method guarantees that all squares will be filled if, at each stage, the knight’s next position is to a square from which the minimum possible number of moves can be made.

For instance, suppose the knight starts in position 1, as shown below.

my-kingdom-for-a-horse

There are three possible squares (labelled 3, 5 and 7) it can jump to as its second move. Which one should it be?

The square numbered 3 means from that position the knight can move to one of three available squares, A, B or C. From the square numbered 7, there are 7 possible locations the knight can move to (A to G), and from the square numbered 5, five positions are available for the knight to occupy.

The strategy is to choose the lowest number, since it represents the hardest to reach square from all the available ones. In this example, it is easier for the night to reach the “7” square than to reach the “5” square or the “3” square.

Hence the first move should be to the square numbered 3.

my-kingdom-for-a-horse

From the knight’s first position, the second move will be to either one of the squares numbered 5. From there, choose the square numbered 1, and so on.

my-kingdom-for-a-horse

Playing knight solitaire has not made me a better chess player, but it has forged a stronger bond between me and the knight.