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 64^{th}
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 64^{th} 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.
