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.

olutions

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 nowrap|8 × 8 board. [cite book
author = Wegener, I.
title = Branching Programs and Binary Decision Diagrams
publisher = Society for Industrial & Applied Mathematics
date = January 1, 1987
isbn = 0-898-71458-3] 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 nowrap|6 × 6 board, and no such tours on smaller boards [ [http://mathworld.wolfram.com/KnightsTour.html Knight's Tour - from Wolfram MathWorld ] ] .

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. [A. Conrad, T. Hindrichs, H. Morsy, and I. Wegener. "Solution of the Knight's Hamiltonian Path Problem on Chessboards." "Discrete Applied Math", volume 50, no.2, pp.125-134. 1994.]

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" [cite book
author = Satyadev, Chaudhary
title = Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);
publisher = Parimal Sanskrit Series No. 30
location = Delhi] 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 nowrap|10 × 10 Knight's Tour which sets the order of the chapters in Georges Perec's novel "".

Schwenk's Theorem

For any nowrap|"m" × "n" 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 nowrap|5 × 5 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 nowrap|odd × odd 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 nowrap|1 × 1).

It can be shown that a nowrap|4 × "n" board cannot have a closed tour.

Start by assuming that a nowrap|4 × "n" 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 nowrap|4 × "n" 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 nowrap|4 × "n" 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. [Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." "Neurocomputing", 4(5):249-254, 1992.] 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)$

::

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.

See also

* Abu-Bakr Muhammad ben Yahya as-Suli
* George Koltanowski
* Longest uncrossed knight's path
* Knight's tour graph

References

* Watkins, John J. Across the Board: the Mathematics of Chessboard Problems. Princeton UP, 2004.

External links

* [http://www.amazon.com/dp/0979763002 - A Knight of Egodeth: Zen Raptured Quietude 240 Solutions to the Knights Tour in form of Game Book, published by Dr. Eugene "Roger" Apodaca]
* [http://web.telia.com/~u85905224/knight/bWarnsd.htm Warnsdorff's rule II - Efficiency of Warnsdorff´s Rule]
* [http://web.telia.com/~u85905224/knight/eWarnsd.htm Warnsdorff's Rule Web Page]
* [http://www.velucchi.it/mathchess/knight.htm The ultimate Knight's Tour page of Links]
* [http://www.borderschess.org/KnightTour.htm The knight's tour]
* [http://www.ktn.freeuk.com/sitemap.htm Knight's tour notes]
* [http://www.compgeom.com/~piyush/teach/3330/homeworks/knightour.cpp A Simple backtracking implementation in C++]
* [http://www.research.att.com/~njas/sequences/A001230 Sloane's Integer Sequence A001230]
* [http://members.cox.net/beagenius/knighttour1.html 8 by 8 Knight's Tour strategy]
* [http://members.cox.net/beagenius/knightquiz.html Playable 8 by 8 Knight's Tour]
* [http://demonstrations.wolfram.com/TheKnightsTour/ The Knight's Tour] by Jay Warendorff based on a program by Arnd Roth, The Wolfram Demonstrations Project.
* [http://dmitrybrant.com/knights-tour Knight's Tours Using a Neural Network] Program that creates tours using a neural network, plus gallery of images.