Dictionary Thesaurus Word Dynamo Quotes Reference Translator Spanish

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.

Solutions

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 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 board, and no such tours on smaller boards .

Variations

Many variations on this topic have been studied by mathematicians, including Euler, over the centuries using:

differently sized boards
two-player games based on this idea
problems using slight variations on the way the knight moves.

Theory

The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory, which is NP-complete. The problem of getting a closed knight's tour is similarly an instance of the hamiltonian cycle problem. Note however that, unlike the general Hamiltonian path problem, the knight's tour problem can be solved in linear time.

History

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

In the 20th century the Oulipo group of writers used it among many others. The most notable example is the Knight's Tour which sets the order of the chapters in Georges Perec's novel Life: A User's Manual.

Schwenk's Theorem

For any board with m less than or equal to n, a closed knight's tour is always possible unless one or more of these three conditions are true:

m and n are both odd
m = 1, 2, or 4; m and n are not both 1
m = 3 and n = 4, 6, or 8

Condition 1

It is not hard to show that when condition 1 is true a closed knight's tour is impossible.

Imagine a chessboard colored black and white in the manner that we are all familiar with (alternating). Whenever a knight moves it lands on the opposite color. If it is on white, it moves to black. If it is on black, it moves to white.

Since m and n are both odd, the number of white squares and black squares are different. For example, in a checkerboard there are 13 of one color and 12 of the other.

For a knight to have a closed tour it must visit the same number of white squares and black squares. But we have just seen that boards have a different number of white squares and black squares, therefore closed tours do not exist. Open tours may still exist.

Condition 2

Condition 2 states that when the shorter side is length 1, 2, or 4, no closed tour is possible.

It is easy to see why when m = 1 or 2 that no knight's tour is possible: the knight would not be able to reach every square (with the exception of the trivial case ).

It can be shown that a board cannot have a closed tour.

Start by assuming that a board has a closed knight's tour. Let us construct 2 sets of squares, $A_1$ and $B_1$ , $A_1$ containing one half of the squares on the board and $B_1$ containing the other half of the squares on the board. If we color this board with a checkerboard pattern, we can define $A_1$ as the set of white squares and $B_1$ as the set of black squares. As previously established, the knight must alternate between white and black ( $A_1$ and $B_1$ ).

Consider the figure on the right. Define $A_2$ as the set of green squares and $B_2$ as the set of red squares in the figure. There are an equal number of red squares as green squares. Note that from a square in $A_2$ the knight must next jump to a square in $B_2$ . And since the knight must visit every square, when the knight is on a $B_2$ square in must move to an $A_2$ next (otherwise the knight will need to make a repeat on an $A_2$ square as well, but this is impossible).

If we follow the knight we will find a contradiction.

The first square the knight goes to will be a square of $A_1$ and $A_2$ . If it is not, we switch $A_2$ and $B_2$ so that it is true.
The second square must be an element of the sets $B_1$ and $B_2$ .
The third square must be an element of $A_1$ and $A_2$ .
The fourth square must be an element of the sets $B_1$ and $B_2$ .
And so on.

It follows that set $A_1$ has the same elements as set $A_2$ , and set $B_1$ has the same elements as set $B_2$ . But this is obviously not true, as the red and green pattern shown above is not the same as a checkerboard pattern; the set of red squares is not the same as the set of black squares (or white, for that matter).

So our above assumption was false and there are no closed knight's tours for and board, for any n.

Condition 3

Condition 3 may be proved using casework. Attempting to construct a closed knight's tour on a 3 by 4, 3 by 6, or 3 by 8 will lead to definite failure.

3 by n boards with n not equal to 4, 6, or 8 can be shown to be possible by using a repeating pattern (i.e., induction).

All other cases

Simply proving the above three conditions does not prove the theorem; it is still required to prove that all rectangular boards that do not fall in one of the above three categories have closed knight's tours.

Neural network solutions

The Knight's Tour problem also lends itself to being solved by a neural network implementation. The network is set up such that every legal knight's move is represented by a neuron, and each neuron is initialized randomly to be either "active" or "inactive" (output of 1 or 0), with 1 implying that the neuron is part of the final solution. Each neuron also has a state function (described below) which is initialized to 0.

When the network is allowed to run, each neuron can change its state and output based on the states and outputs of its neighbors (adjacent knight's moves) according to the following transition rules:

U_{t+1} (N_{i,j}) = U_t(N_{i,j}) + 2 - sum_{N in G(N_{i,j})} V_t(N)

V_{t+1} (N_{i,j}) = left{ begin{array}{ll} 1 & mbox{if},, U_{t+1}(N_{i,j}) > 3 0 & mbox{if},, U_{t+1}(N_{i,j}) < 0 V_t(N_{i,j}) & mbox{otherwise}, end{array} right.

where $t$ represents discrete intervals of time, $U(N_{i,j})$ is the state of the neuron connecting square $i$ to square $j$ , $V(N_{i,j})$ is the output of the neuron from $i$ to $j$ , and $G(N_{i,j})$ is the set of neighbors of the neuron.

Although divergent cases are possible, the network should eventually converge, which occurs when no neuron changes its state from time $t$ to $t+1$ . When the network converges, a solution is found. The solution found by the network will be either a knight's tour, or a series of two or more independent knight's tours within the same board.