Awatmath.2109
net.chess,net.math
utcsrgv!utzoo!decvax!watmath!dthedmonds
Mon Mar 22 21:49:24 1982
Knight's Tour
The Knight's Tour
=================
The knight's tour is an old chess problem which involves moving
a knight (as in the chesspiece) from one corner of a rectangular
checkerboard to the diagonally opposite corner, visiting every
square on the board once and only once. For example, the solution
for a 3x4 board is as follows (S is for start, F for finish):
---------------------------------
| S | 3 | 6 | 9 |
---------------------------------
| 7 | 10 | 1 | 4 |
---------------------------------
| 2 | 5 | 8 | F |
---------------------------------
Now, if we number the positions of our board as follows:
---------------------------------
| 0 | 1 | 2 | 3 |
---------------------------------
| 4 | 5 | 6 | 7 |
---------------------------------
| 8 | 9 | 10 | 11 |
---------------------------------
then the solution above visited the squares in the following order:
0,6,8,1,7,9 2,4,10,3,5,11
Note that the first+last = 11, second + second-to-last = 11,...etc.
I call this a symmetric solution, that is:
Given a rectangular board with M=2N or M=2N+1 squares
and we number our moves 0 to M-1 then the sum of the
Ith position and the (M-1)-Ith position = M-1.
It is my belief that if, for a given board, there exists one or more
solutions then at least one of those solutions must be symmetric.
Using an algorithm based on this belief I have determined that there
is no symmetric solution for either the 4x4 or the 6x6 board.
Can anyone out there supply me with a proof that my theory is correct
or a counter-example to show I'm wrong?
Thanx from Dean at
!decvax!watmath!dthedmonds
-----------------------------------------------------------------
gopher://quux.org/ conversion by John Goerzen <
[email protected]>
of
http://communication.ucsd.edu/A-News/
This Usenet Oldnews Archive
article may be copied and distributed freely, provided:
1. There is no money collected for the text(s) of the articles.
2. The following notice remains appended to each copy:
The Usenet Oldnews Archive: Compilation Copyright (C) 1981, 1996
Bruce Jones, Henry Spencer, David Wiseman.
