On a normal 8x8 chessboard, find a complete Knight's Tour.

A Knight's move is as in chess, an L shaped move, 2 squares in one direction and 1 square in the other direction.)

A Knight's Tour is one where the knight passes through each square exactly once.

You may start on any square you wish.

* For extra credit, come up with a re-entrant tour: at the end, the knight is exactly one knight's move away from the starting square.

* For EXTRA extra credit, make sure that the path is, in some way, symmetrical.
_______________________

Since "Knight's Tour" is a term used outside the scope of this problem, I'm sure you can find an answer on the internet. Please find an independent solution.

This does not require a computer program.

If the square in the ith row and jth column is designated a(i,j), there are seven possible "mirrors" for a given square a(i,j) (Some of these may point to a(i,j) or to an earlier mirror, resulting in fewer actual mirrors.)
a(i,j)=a(i,j)
b(i,j)=a(9-i,j)
c(i,j)=a(i,9-j)
d(i,j)=a(9-i,9-j)
e(i,j)=a(j,i)
f(i,j)=a(9-j,i)
g(i,j)=a(j,9-i)
h(i,j)=a(9-j,9-i)

Note: There are 10 mutually exclusive sets of squares such that for each square in a given set, all of its mirrors are in the set, but no non-mirrors:

0 1 2 3 3 2 1 0
1 4 5 6 6 5 4 1
2 5 7 8 8 7 5 2
3 6 8 9 9 8 6 3
3 6 8 9 9 8 6 3
2 5 7 8 8 7 5 2
1 4 5 6 6 5 4 1
0 1 2 3 3 2 1 0

If the symmetry is physical, then in one of these mirroring schemes, x(i,j), it is true that a jump connects a(i1,j1) to a(i2,j2) iff a jump connects x(i1,j1) to x(i2,j2).

If the symmetry is temporal, then the sequence of jumps can be shifted to start at a square (Due to the re-entrant condition, any valid sequence can be shifted to start on any given square.) such that:
Given n = the number of the jump which lands on a(i,j),
and m = the number of the jump which lands on x(i,j),
Either n - m = ±32 or n + m = 0(mod 64).

The first temporal symmetry condition (n - m =±32) always results in a physical symmetry, and does not need to be considered separately.

The second temporal symmetry condition [n + m = 0 (mod 64)] may also always result in a physical symmetry, but I have not tested it enough to be sure.

Notice that in the second temporal symmetry condition x(i,j)=a(i,j) for the squares at n=0 and n=32.

Conjecture: Except for the corner case [where, for example a(1,1) must connect with both a(2,3) and a(3,2)], the two squares any given square connects with cannot be in the same mirror set. For example, a(5,5) cannot connect to both a(6,7) and a(7,6) because they are both in mirror set 5.

(Edited to correct a minor typo)
Edited on March 7, 2004, 9:45 pm

Posted by TomM on 2004-03-07 18:27:31