Knight's Tours on a Torus
John J. Watkins, Rebecca L. Hoenigman · Mathematics Magazine · 1997
The knight is the only piece in chess that does not move in a straight line. Instead, it moves in an L-two squares in either a vertical or horizontal direction and then one square in a perpendicular direction. It is the strangeness of this move that has made the Knight's Tour Problemn one of the most intriguing in all of recreational mathematics: Can a knight visit each square of a chessboard by a sequence of knight's moves, andfinish on the same square as it began? Since a chessboard can be represented as a graph in which each vertex corresponds to a square, and edges correspond to those pairs of squares connected by a knight's move (FIGURE 1 illustrates this for a 4 x 4 board), finding a knight's tour amounts to finding a Hamiltonian cycle in the corresponding graph, a notoriously difficult general problem in graph theory (see [5]). However, we can easily see that there is no knight's tour for a 4 x 4 board since any Hamiltonian cycle would have to include the four edges incident to the two corner vertices indicated in FIGURE 1; this is impossible since these four edges already form a cycle that includes only four vertices.