## 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.)

There have been 4588 visitors to this page since May 16, 2000
.

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

©Frank Ruskey, 1995-2003.