The Knight’s Tour

The Knight’s Tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once.

There are a great many solutions to the problem, of which exactly 26,534,728,821,064 have the knight finishing on a square from which it attacks the starting square, on an 8 × 8 board. Such a tour is described as directed and closed. (A directed tour is a directed graph: the direction of the tour is specified. A closed tour is one that ends on the starting square.) The number of undirected closed tours is half this number, since every tour can be traced in reverse. Otherwise the tour is open (as in the first diagram). There are 9,862 undirected closed tours on a 6 × 6 board, and no such tours on smaller boards.

113

The pattern of a Knight’s Tour on a half-board has been presented in verse form (as a literary constraint) in the highly stylized Sanskrit poem Kavyalankara[4] written by the 9th century Kashmiri poet Rudrata, which discusses the art of poetry, especially with relation to theater (Natyashastra). As was often the practice in ornate Sanskrit poetry, the syllabic patterns of this poem elucidate a completely different motif, in this case an open knight’s tour on a half-chessboard.

The first algorithm for completing the Knight’s Tour was Warnsdorff’s algorithm, first described in 1823 by H. C. Warnsdorff.

Be Sociable, Share!
Tags: ,

About Android