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.
Note that there is only one way to access squares like a1, a8, h1, and h8. This means that if your knight ever lands on a square like b3, c2, b6, c7, f2, g3, f7, or g6 his next move must include the corner square followed by the opposite exit square.
If we are aiming for SK's extra credit than we are seeking a 64 move pattern which ends where it begins, and as such makes the starting square irrelavant. Also if we are seeking to earn his EXTRA extra credit we might imagine a symmetry where each corner is hit with equal distribution.
I put the numbers 1, 17, 33 and 49 in each of the corners in order counter-clockwise but this fails when I notice that the knight must alternate black and white squares. Therefore the symmetry must be balanced over the breadth of 32 moves as opposed to 16.
Posted by Eric
on 2004-03-06 14:20:30