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 Anum=A003192"> A003192(M1369) in

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 Anum=A006075"> A006075(M3224) in

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:



It was last updated .