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 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.