Knight's Tours
Advisor: Mark Krusemeyer |

As the following diagram shows, both anwers are "Yes" for the 8 x 8 chessboard.

The next important question is this: For what dimensions m x n of a chessboard does an open tour exist? What about a closed tour? These two questions are the basis of this entire project. The results are summarized here, with a full proof following.

Proof (Closed Tours):

First, the trivial cases 1 x n and 2 x n are obvious. I will not go into a useless debate over whether the 1 x 1 board should be considered a closed tour.

Second, m x n boards where m and n are both odd. Consider the colors of the squares of the board (they form an alternating pattern, as on the regular chessboard). Every time the knight moves, it moves to a square of the opposite color. In a closed tour, the last move is back to the first square of the tour. Since the color of the square the knight was on changed each time it moved, and it ended on the same color square, it must have moved an even number of times. But since m and n are both odd, the total number of squares, mn, is odd, so the knight must have moved an odd number of times. It is very difficult for a knight to move an even and an odd number of times simultaneously.

Third, 4 x n boards. Color the board in the following way:

Fourth, the 3 x 4 board. Consider the following diagrams:

Fifth, the 3 x 6 board. Consider the following diagrams:

Sixth, the 3 x 8 board. Consider the following diagrams:

BK and PK are not both moves in the tour; otherwise, there would be the closed loop APKBOJA. Without loss of generality, say BK isn't a move in the tour. Then BQ must be.

PC is not a move in the tour; otherwise, BQHCPKB would be a closed loop. So PK is a move.

LF and LT are not both moves in the tour; otherwise, LFUMGTL would be a closed loop. So LC is a move in the tour.

Finally, DS and RE are both moves in the tour, since nothing other than E and S are accessible to R and D, respectively. But now IDSNERI is a closed loop. Since this was a construction of a general closed tour given the assumption that one existed, there is no closed tour on the 3 x 8 board.

Now we prove that there is a closed tour for all other m x n boards. First, notice the following boards with closed tours:

3x10 | 3x12 |

Now comes the inductive step. Assume a 3 x n closed tour exists. Then a 3 x (n + 4) closed tour also exists, and can be constructed as shown above. 3 x 10 and 3 x 12 closed tours exist (and are shown above). Therefore a 3 x n closed tour exists if n >= 10, even. Such a tour can be constructed by gluing the above 3 x 4 open tour to a closed 3 x 10 or 3 x 12 closed tour a certain number of times:

Such a 4 x n open tour can be added to an m x n closed tour to get a (4 + m) x n closed tour:

6x5 | 6x6 |

6x7 | 6x8 |

8x5 | 8x6 |

See 6x8 | |

8x7 | 8x8 |

A 6 x n closed tour exists, n >= 5.

(Base cases: 6 x 5, 6 x 6, 6 x 7, and 6 x 8 closed tours.)

An m x n closed tour exists, m = 6 + 4k, k = 0, 1, 2, ...; n >= 5.

(Base cases: 6 x n closed tour, n >= 5.)

An 8 x n closed tour exists, n >= 5.

(Base cases: 8 x 5, 8 x 6, 8 x 7, and 8 x 8 closed tours.)

An m x n closed tour exists, m = 8 + 4k, k = 0, 1, 2, ...; n >= 5.

(Base cases: 8 x n closed tour, n >= 5.)

Combining these, we get that an m x n closed tour exists, m >= 6, even; n >= 5.

All boards have now been classified conclusively as having a closed tour or having no closed tour. The proof is complete.

Proof (Open Tours):

Just as for closed tours, 1 x n and 2 x n boards obviously do not have open tours. The 3 x 3 board also contains no open tour. Consider the center square. There is no way for the knight to move to/from that square, so there is no open tour.

The 3 x 5 board does not have an open tour. Consider the following diagram:

The 3 x 6 board does not have an open tour. Consider the following diagram:

The 4 x 4 board, surprisingly, has no open tour. Consider the following diagram:

Now all that is left is to prove that the list of open tours that do exist is correct. Consider these open tours:

3x7 | 3x8 |

3x9 | 3x10 |

Consider these open tours:

4x5 | 4x6 |

4x7 | 4x8 |

5x5 | 5x7 |

A 5 x n open tour exists, n >= 5, odd.

(Base cases: 5 x 5 and 5 x 7 open tours.)

An m x n open tour exists, m = 5 + 4k, k = 0, 1, 2, ...; n >= 5, odd.

(Base cases: 5 x n open tour, n >= 5.)

A 7 x n open tour exists, n >= 5.

(Base cases: 7 x 3 and 7 x 5 open tours.)

An m x n open tour exists, m = 7 + 4k, k = 0, 1, 2, ...; n >= 3, odd.

(Base cases: 7 x n open tour, n >= 3.)

Combining these, we get that an m x n open tour exists, m >= 5, odd; n >= 5, odd. If we use the results from the closed tours (an m x n closed tour exists for m >= 5; n >= 6, even), we get that an open m x n tour exists for m >=5, n >= 5. But we have shown that a 4 x n open tour exists, n >= 5. So an m x n open tour exists for m >=4, n >=5. This concludes the proof.

p.s. We made a program to help find tours on certain large boards (8x8, 7x8, etc. you don't want to do it by hand) in C++. E-mail to amosyang@yahoo.com if you are interested in finding out more about this program. :)