[Information Index] [Generation Index] [COS homepage]

Information on the n Knight's Tour Problem

The problem is to find a tour of a knight on a n by n board. Only valid moves of a knight are allowed and every square of the board must be visited exactly once. If it is possible to use a single valid move to get from the last visited square to the first, then the tour is said to be re-entrant. Below we show three solutions on a standard 8 by 8 board. The chessboard is encoded as shown below for n = 6. 
     0  1  2  3  4  5
  +-------------------
0 |  0  1  2  3  4  5
1 |  6  7  8  9 10 11
2 | 12 13 14 15 16 17
3 | 18 19 20 21 22 23
4 | 24 25 26 27 28 29
5 | 30 31 32 33 34 35
The one-line notation simply gives a list of size n*n of the successive square visited. In matrix notation the ending square of the ith move is labelled with an i.

A related problem is that of finding the longest "uncrossed" knight's tour. For n = 3,4,5,6,7,8 the longest tours have length 2, 5, 10, 17, 24, 35. This is sequence A003192(M1369) in Neil J. Sloane's database of integer sequences.

Another related problem is that of finding the minimal number of knights needed to attack (or occupy) every square of an n by n board. For n = 1,2,...,12 the minimal numbers are 1, 4, 4, 4, 5, 8, 10, 12, 14, 16, 21, 24. This is sequence A006075(M3224) in Neil J. Sloane's database of integer sequences.

The algorithm used is a well-known backtracking. Only inputs to n = 7 are allowed. If any user knows of a fast algorithm that will give lots of solutions for n = 8 (or higher) in a reasonable amount of time, please contact us.

Programs available:
Online Stuff:
[Information Index] [Generation Index] [COS homepage]
Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
There have been 3741 visitors to this page since May 16, 2000 .
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
©Frank Ruskey, 1995-2003.