A Knight's Tour can be solved from any square on the board. There are a couple of ways to solve the puzzle.

• Plan each move carefully, in advance, so you don't get boxed in.
• Use math to calculate the moves.
• Use the cheat sheet!

How to Plan Your Moves

Plan at least 64 moves in advance. As the game progresses it is very important to be careful. As a rule of thumb, always jump to the square with the least exits. To complete the tour, your last move will be in a position that would allow a jump to the square you started in! Good luck, you'll need it!

For Rocket Scientists Only

Mathematically, the knight's tour quandary reduces to finding a "Hamiltonian cycle" in a graph. A graph is a collection of dots, called nodes, joined by lines, called edges. A Hamiltonian cycle is a closed path that visits each node exactly once. The graph of a chessboard is obtained by placing a node at the center of each square and then drawing edges between nodes that are separated by one knight's move. It helps to color the nodes dark and light, corresponding to the usual pattern on a chessboard. Notice that when the knight moves, it hops from a node of one color to one of the opposite color, so the nodes must be alternately dark and light around any Hamiltonian cycle. This pattern implies that the total number of nodes must be even. If the chessboard were 3 X 5, with 15 nodes (an odd number), we have proved that no knight's tour is possible on such a chessboard. The same is true for any rectangular board of size m X n where both m and n are both odd.

This kind of argument is known as a parity proof. A more subtle parity proof, invented by Louis Posa, demonstrates that there is no closed knight's tour on any 4 x n board. Allen Schwenk provided a characterization of those rectangular boards that support a knight's tour. He found that an m X n chessboard (when m is less than or equal to n) supports a knight's tour unless:

• m and n are both odd
• m = 1, 2 or 4
• m =3 and n = 4, 6 or 8

You can try this by taking a peice of graph paper out, make a small board with 5 X 6 nodes (dots) and then connecting them with edges (lines).

  

                             n 



                         A B C D E F 

                         G H I J K L

                   m     M N O P Q R

                         S T U V W X

                         Y Z 1 2 3 4

A-N-Y-U-3-R-E-P-1-S-H-D-L-W-J-F-Q-4-V-Z-M-B-O-2-X-K-C-G-T-I and back to A!

A completed Hamiltonian cycle!

There are nine graphs which supply the templates from which, by extension, all other knight's tours can be constructed. They are 5 X 6, 6 X 6, 5 X 8, 8 X 8, 8 X 6, 7 X 6, 7 X 8, 10 X 3 and 12 X 3. Can you solve these?

You can try this out on the Knight's Tour page by attempting to create the Hamiltonian cycle on different shaped boards.

So you ask, what good is all this. Well, what if you were in charge of scheduling an airline's route, or a satelite's visit to the planets, or even your paper-route? Math is everywhere, play with it, have fun with it and learn it!.