## 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 *i*th 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:
- Mathworld's entry on Knight Tours.

**Questions??** Email
The wizard of COS.

(Please note that the suffix XXXX must be removed from the preceeding
email address.)

[Error Opening Counter File -- Click for more info]

It was last updated Wednesday, 10-May-2006 10:32:14 PDT.

©Frank Ruskey, 1995-2003.