[blind-chess] Chess Article #47 The Knight's Tour

From: Roderick Macdonald <rmacd@xxxxxxxx>
To: Blind Chess Mailing List <blind-chess@xxxxxxxxxxxxx>
Date: Wed, 9 Jun 2010 19:36:20 -1000 (HST)
Chess Article #47
The Knight's Tour

The Knight's Tour is a chess puzzle/mathematical problem involving
a Knight on a chessboard. The Knight is placed on any square on the
empty board and, moving according to the rules of chess, must visit
each square exactly once. A Knight's tour is called a closed tour
if the Knight ends on a square attacking the square from which it
began (so that it may tour the board again immediately with the
same path). Otherwise the tour is open. Creating a program to solve
the Knight's tour is a common problem given to computer science
students.

How difficult is it to "solve" the Knight's tour? In an article
from Chessbase Magazine, Frederic Friedel relates the following
story:

"In February 2003 a nine-year-old boy caused a minor sensation on
German TV. It was on the show "Wetten dass..?", which translates
approximately to "Want to bet..?" The format is that a series of
candidates propose to be able to do impossible feats, live and in
front of the camera. For instance uncork a bottle of wine using a
corkscrew attached to the landing gear of a helicopter.

The boy on the show was Xaver Neuhdusler from the state of Bavaria,
and the bet was that this young lad could complete a "Knight's
tour" of the chessboard, completely in his head, starting from any
square on the board.

A "Knight's tour" is a sequence of 64 Knight moves executed in such
a way that each square of the board is visited exactly once. Xaver
was blindfolded and a starting square was called out to him.
Without much ado the lad dictated a sequence of 64 squares that
comprised a perfect Knight tour.

The reaction to this feat in Germany was overwhelming. Newspapers
were full of it, people discussed it on trains and busses, in
offices and schools, and we received dozens of calls asking us to
tell the story on our web site."

Friedel later tells tells the story of his own first encounter with
an Knight's tour exhibition:

"It happened many years ago, at a US chess club, where a blindfold
master was giving a demonstration of his extraordinary abilities.
At one stage he asked for a helper from the audience, and I was
pushed and poked by my friends to take the stage. There the master
gave me a block of sticky notes and asked me to write down names,
words and numbers dictated at random by the audience. Each was
stuck on a big demo chessboard, starting from the square a8 and
working sequentially to h1.

The audience call out a variety of words: names of cities, family
members, phone numbers, abstract expressions. It went something
like: Dayton, Margaret-Lee Farrow, pride before a fall,
212-783-4529, my dad's dog Skippy. While this was going on the
master sat on his chair, listening to the audience, chatting with
them. He was completely relaxed and not making any visible effort
to memorise the notes.

After all the squares had been covered the master was blindfolded.
He then asked someone in the audience to name a square on the
chessboard. Starting from that square he started repeating words
and numbers, while I removed the corresponding sticky notes from
the demo board. The order of the words resulted in a perfect
Knight's tour. I believe he got one or two words slightly wrong, on
the lines of Margaret-Mae Farrow instead of Margaret-Lee. All the
numbers were perfect.

Now that is a truly remarkable feat. We were all deeply impressed,
not the least because the master was approaching ninety years in
age! He was George Koltanowski, one of the greatest mental acrobats
the world has ever seen.

How many Knight's tours are there?

The number of Knight's tours that are possible on a normal
chessboard is surprisingly big. Actually it is so big that simple
counting of tours is out of reach even for the fast computers of
today. The problem has to be tackled in other ways. In 1995 Martin
L`obbing and Ingo Wegener proclaimed that "the number of Knight's
tours equals 33,439,123,484,294". They obtained this result by
running 20 Sun workstations for four months.

In 1997 Brendan McKay used another method (splitting the board into
two halves) and got the result 13,267,364,410,532.

To give you an idea of the magnitude of these numbers, a computer
searching and finding tours at a speed of one million tours per
minute would need more than 25 years to calculate the number of
tours given by McKay.

However, on an 8x8 board, there are exactly 26,534,728,821,064
directed closed tours (i.e. two tours along the same path that
travel in opposite directions are counted separately). There are
9,862 undirected closed tours on a 6x6 board. No closed tours exist
for smaller square boards.

Note that for any closed Knight's tour, the exact same path can be
used from any one of the 64 squares, and also in either direction,
so that one closed tour path represents 128 possible tours.

Variations of the Knight's tour problem involve chessboards of
different sizes than the usual 8x8, as well as irregular (non-
rectangular) boards.

OK, so what's the answer? Just one???

Here is an example of a Knight's Tour:
Place a Knight on the e1 square:
1. Ng2
2. Nh4
3. Ng6
4. Nh8
5. Nf7
6. Nh6
7. Ng4
8. Nh2
9. Nf1
10. Nd2
11. Nb1
12. Na3
13. Nb5
14. Na7
15. Nc8
16. Ne7
17. Ng8
18. Nf6
19. Nh7
20. Ng5
21. Nf3
22. Nd4
23. Nf5
24. Nd6
25. Ne8
26. Nc7
27. Na8
28. Nb6
29. Na4
30. Nb2
31. Nd1
32. Nf2
33. Nh1
37. Ng3
35. Nh5
36. Ng7
37. Ne6
38. Nf8
39. Nd7
40. Nb8
41. Na6
42. Nb4
43. Na2
44. Nc1
45. Ne2
46. Ng1
47. Nh3
48. Nf4
49. Nd3
50. Nc5
51. Ne4
52. Nc3
53. Nd5
54. Ne3
55. Nc4
56. Ne5
57. Nc6
58. Nd8
59. Nb7
60. Na5
61. Nb3
62. Na1
63. Nc2
64. Ne1


References:
Wikipedia, the Free Encyclopedia
http://www.chessbase.de/
==========The blind-chess mailing listView list information and change your settings: //www.freelists.org/list/blind-chessList archives: //www.freelists.org/archives/blind-chess=========
[blind-chess] Chess Article #47 The Knight's Tour

Other related posts:
