Frezcogames

Developer of the boardgame Freeze

Solving a Knight's Tour Blindfolded
 
 
We begin with a little story...

The Great Frezco

“Ladies and gentlemen. The knight's tour is one of the oldest known puzzles. In it, a chess knight is placed on an otherwise empty chessboard and then maneuvered about the board in such a way that it lands on every square once and only once. This is not an easy task.

“But to your astonishment, I, the great Frezco, will now solve a knight's tour without even looking at a board!”

Gasps and exclamations of amazement are heard from the audience. There is some fainting.

The great Frezco's assistant blindfolds him as he continues, “Will someone in the audience give me the knight's first square? Any square at all.”

A voice calls out, “How about e3?”

“Good. The knight will begin on e3, and my assistant will now go to the demonstration board and mark that square with the number one. Now, to make my task even more difficult, I will also ask someone in the audience to pick the 64th square. But first, we must consider the fact that the square e3 is a dark colored square, and as you may know, a knight that's on a dark square will move to a light square, then a dark one, then a light one, etcetera, etcetera. Therefore in this tour, all the dark squares will receive odd numbers, and all the light squares will receive even numbers. So, will someone suggest a light colored square for the knight's final position? Any light colored square will do.”

Another voice calls out, “c8.”

“Very well, then. My assistant will write the number 64 on the square c8. Now please allow me a moment to consider this task, and please remain quiet as I announce the moves.”

 

The great Frezco gathers his thoughts and after some seconds begins to call out the coordinates for the squares. His assistant writes consecutive numbers on the demonstration board as the squares are named.

“e3 – d5 – f6 – h5 – g7 – e8 – c7 – a8 – b6 – a4 – b2 – d1 – c3 – e4 – g3 – h1 – f2 – d3 – f4 – h3 – g1 – e2 – c1 – a2 – b4 – a6 – b8 – d7 – f8 – h7 – g5 – e6 – c5 – b3 – a1 – c2 – e1 – g2 – h4 – g6 – h8 – f7 – d8 – b7 – a5 – c6 – e5 – f3 – d4 – f5 – e7 – g8 – h6 – g4 – h2 – f1 – d2 – b1 – a3 – c4 – d6 – b5 – a7 – and square number 64 is c8 as planned.”

The great Frezco removes the blindfold and points to the demonstration board which now looks like this:

 
Those in the audience who have not fainted give the great Frezco a standing ovation. He bows and leaves the stage.
 

Multiple choice question:

How did Frezco do it?

a - The people calling out from the audience were plants. He had this knight's tour memorized.

b - The great Frezco is a chess genius. He can visualize the entire board and plan ahead 64 moves.

c - Frezco has learned how to divide the board up into easily recognizable patterns, how to find his way around a pattern, and how to switch from one to another. Once he determined which pattern e3 belongs to and which one c8 belongs to, everything quickly fell in place.

The correct answer is c. There were no plants, and Frezco is merely a pretty good chess player.

Frezco's technique

First, divide the board into quadrants.

 

Note that each quadrant looks the same (they do, of course, relate to each other differently).

In the story, Frezco had to state that e3 was a dark colored square, and he had to verify that c8 was light colored. We'll look at 2 easy ways to do this. One's a chessboard way and the other uses a math trick.

Chessboard way: Each quadrant has a long diagonal of light squares and a long diagonal of dark squares. The 8 squares that don't belong to the long diagonals are all vertically or horizontally adjacent to one of the corner squares. It's easy to “see” that e4 is on the long diagonal of light squares. Since e3 is vertically adjacent to e4, it must be dark. And c8 is horizontally adjacent to d8, so it must be light.

Math trick way: Convert the letter coordinates to numbers (a = 1, h = 8). If one of a square's coordinates is an odd number and the other is even, the square is light. Otherwise, the square is dark. Using this technique, e3 is converted to 53. Both digits are odd, so e3 is dark. And c8 is converted to 38. One digit is odd and the other is even, so c8 is light.

Don't worry. Once you get to the business of actually solving the tour, you won't have to keep track of the colors.

Now for the patterns:

 
The above pattern is the “right diamond.” It leans to the right.
 

 
 
Above is the “left diamond.” The left and right diamonds are mirrors of each other.
 

 
 
Above is the “right wheel.” Other people call this the right square, but Frezco prefers to call it a wheel because the chessboard already has squares, and he likes to picture the knight rolling around the edges of the quadrant.
 

 

And this is the “left wheel.” The left and right wheels are mirrors of each other.

 
The four patterns take care of all the squares in a quadrant. Each square belongs to only one of the patterns:

 
Here's what the whole board looks like when it's divided into quadrants and marked with the patterns:
 

 

Some observations:

A knight can't visit all the squares in a quadrant in 16 consecutive moves. It has to leave the quadrant and come back to it later.

It's not possible to switch directly from a pattern to its mirror. You can switch to either of the other patterns, but not to the mirror.

Each pattern in each quadrant has one square that is closest to the center of the board. Usually, you'll have more options if you end a pattern on one of those squares.

The 4 squares in the middle of a quadrant can be used to change patterns while remaining in the quadrant.

Access to the board's corner squares (a1, a8, h1, and h8) is limited. If a corner square has not been visited, and it's not the tour's 64th square, the knight must go to the corner when it's a move away.

Quadrant Hopping:

It's possible to move through the less centralized squares in a pattern and into the next quadrant, saving one or more of the centralized squares for later. It's also possible to do the reverse, moving through several of the centralized squares and then visiting the less centralized ones. There are 2 reasons to quadrant hop:

1. Quadrant hop to hide what you're doing. Consider this start of a tour:
 

 
The right diamond is played in its entirety 4 times, giving an observer a pretty good chance to spot it.  Here's a different way to get from a1 to f3:
 

We again have 4 right diamonds, but the quadrant hopping has masked this fact to some extent.

2. Quadrant hop to end on a particular square.

Try this yourself. Pick a pattern, any pattern. Make square one any square in the pattern. Pick any square of the other color in the same pattern and make that square 16. Complete the pattern starting on square 1 and ending on square 16. (This is a good exercise. Repeat it as often as you like.)

Solving a tour

There are three categories of knight's tours:

Category 1

Tours that end in a different pattern from the starting one, but not the starting pattern's mirror. (Example: starts in the left wheel and ends in the right diamond.) Half of the tours are in this category.

Recommended technique for category 1 tours: complete the starting pattern, complete the mirror of the ending pattern, complete the starting pattern's mirror, go to the ending pattern and quadrant hop as needed to square 64. (Back to the example: complete the left wheel, complete the left diamond, complete the right wheel, complete the right diamond, quadrant hopping as needed.)

 

Category 2

Tours that end in the starting pattern's mirror. (Example: starts in the left diamond and ends in the right diamond.) A quarter of the tours are in this category.

Recommended technique for category 2 tours: leave the starting pattern before completing it, complete one of the other patterns, return to the starting pattern and complete it, complete the next available pattern, go to the mirror of the starting pattern and quadrant hop as needed to square 64. (Back to the example: leave the left diamond, complete the right wheel, complete the left diamond, complete the left wheel, complete the right diamond, quadrant hopping as needed.)

 

Category 3

Tours that end in the starting pattern. (Example: starts and ends in the right wheel.) A quarter of the tours are in this category.

Recommended technique for category 3 tours: leave the starting pattern, complete either of the next available patterns, complete the starting pattern's mirror, complete the next available pattern, return to the starting pattern and quadrant hop as needed to square 64. (Back to the example: leave the right wheel, complete the left diamond, complete the left wheel, complete the right diamond, complete the right wheel, quadrant hopping as needed.)

 

The tour that Frezco solved in the story was also a category 3, starting and ending in a right wheel. He usually would have completed one quadrant of the wheel before switching patterns, but he felt adventurous and left the wheel immediately. He found this a little more challenging because he had to remember that when returning to the right wheel, only the less centralized squares in the lower right quadrant remained.

 
Solving a tour blindfolded

No promise here, but if you use this technique to solve a knight's tour with pencil and paper, there's a good chance you'll soon be able to do it without looking at a board. Solve one tour of each category, writing the numbers 1 to 64 on a chessboard diagram. Do that for several days. Then try it without a board. If you feel you need more practice:

1 - Solve a tour with pencil and paper.

2 - Go over the tour move by move, noting each square's coordinates.

3 - Try recalling the tour without looking at the board.

Another exercise: see “Quadrant hop to end on a particular square” above. Try doing this without looking at a board.

In a matter of days (hopefully), you'll have mastered the trick!

The great Frezco bows and leaves the page.

© 2009 Frezcogames

 
As noteworthy as the above may be, Frezco does not regard it as his crowning achievement.  For that, see the boardgame Freeze