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 <jgoerzen@complete.org>
 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.