HOME

TheInfoList



OR:

A knight's tour is a sequence of moves of a
knight A knight is a person granted an honorary title of knighthood by a head of state (including the Pope) or representative for service to the monarch, the Christian denomination, church or the country, especially in a military capacity. Knighthood ...
on a
chessboard A chessboard is a used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During play, the bo ...
such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed (or re-entrant); otherwise, it is open. The knight's tour problem is the
mathematical problem A mathematical problem is a problem that can be represented, analyzed, and possibly solved, with the methods of mathematics. This can be a real-world problem, such as computing the orbits of the planets in the solar system, or a problem of a more ...
of finding a knight's tour. Creating a
program Program, programme, programmer, or programming may refer to: Business and management * Program management, the process of managing several related projects * Time management * Program, a part of planning Arts and entertainment Audio * Programm ...
to find a knight's tour is a common problem given to
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
students. Variations of the knight's tour problem involve chessboards of different sizes than the usual , as well as irregular (non-rectangular) boards.


Theory

The knight's tour problem is an instance of the more general
Hamiltonian path problem In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or ...
in
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
. The problem of finding a closed knight's tour is similarly an instance of the
Hamiltonian cycle problem In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or ...
. Unlike the general Hamiltonian path problem, the knight's tour problem can be solved in
linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
.


History

The earliest known reference to the knight's tour problem dates back to the 9th century AD. In Rudrata's (5.15), a Sanskrit work on Poetics, the pattern of a knight's tour on a half-board has been presented as an elaborate poetic figure () called the or 'arrangement in the steps of a horse'. The same verse in four lines of eight syllables each can be read from left to right or by following the path of the knight on tour. Since the Indic writing systems used for Sanskrit are syllabic, each syllable can be thought of as representing a square on a chessboard. Rudrata's example is as follows: transliterated: For example, the first line can be read from left to right or by moving from the first square to the second line, third syllable (2.3) and then to 1.5 to 2.7 to 4.8 to 3.6 to 4.4 to 3.2. The Sri Vaishnava poet and philosopher
Vedanta Desika Vedanta Desikan (1268–1369), also rendered Vedanta Desikar, Swami Vedanta Desikan, and Thoopul Nigamaantha Desikan, was an Indian polymath who wrote philosophical as well as religious and poetical works in several languages, including Sa ...
during the 14th century in his 1,008-verse magnum opus praising Lord
Ranganatha Ranganatha, also known as Ranganathar, Rangan, Aranganathar, Sri Ranga, and Thenarangathan, is a Hindu deity with his origin in South India, serving as the chief deity of the Sri Ranganathaswamy Temple, Srirangam. The deity is a resting form o ...
's divine sandals of Srirangam; i.e., Paduka Sahasram (in chapter 30: ''Chitra Paddhati'') has composed two consecutive
Sanskrit Sanskrit (; attributively , ; nominally , , ) is a classical language belonging to the Indo-Aryan languages, Indo-Aryan branch of the Indo-European languages. It arose in South Asia after its predecessor languages had Trans-cultural diffusion ...
verses containing 32 letters each (in Anushtubh meter) where the second verse can be derived from the first verse by performing a Knight's tour on a board, starting from the top-left corner. The transliterated 19th verse is as follows: The 20th verse that can be obtained by performing Knight's tour on the above verse is as follows: sThi thA sa ma ya rA ja thpA ga tha rA mA dha kE ga vi , dhu ran ha sAm sa nna thA dhA sA dhyA thA pa ka rA sa rA , , It is believed that Desika composed all 1,008 verses (including the special ''Chaturanga Turanga Padabandham'' mentioned above) in a single night as a challenge. A tour reported in the fifth book of Bhagavantabaskaraby by Bhat Nilakantha, a cyclopedic work in Sanskrit on ritual, law and politics, written either about 1600 or about 1700 describes three knight's tours. The tours are not only reentrant but also symmetrical, and the verses are based on the same tour, starting from different squares. Nilakantha's work is an extraordinary achievement being a fully symmetric closed tour, predating the work of Euler (1759) by at least 60 years. After Nilakantha, one of the first mathematicians to investigate the knight's tour was
Leonhard Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries ...
. The first procedure for completing the knight's tour was Warnsdorf's rule, first described in 1823 by H. C. von Warnsdorf. In the 20th century, the
Oulipo Oulipo (, short for french: Ouvroir de littérature potentielle; roughly translated: ''"workshop of potential literature"'', stylized ''OuLiPo'') is a loose gathering of (mainly) French-speaking writers and mathematicians who seek to create work ...
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 ''Life A User's Manual'' (the original title is ''La Vie mode d'emploi'') is Georges Perec's most famous novel, published in 1978, first translated into English by David Bellos in 1987. Its title page describes it as "novels", in the plural, the ...
''. The sixth game of the
World Chess Championship 2010 The World Chess Championship 2010 match pitted the defending world champion, Viswanathan Anand, against challenger Veselin Topalov, for the title of World Chess Champion. The match took place in Sofia, Bulgaria from 24 April to 13 May 2010, with ...
between
Viswanathan Anand Viswanathan "Vishy" Anand (born 11 December 1969) is an Indian chess grandmaster and a former five-time World Chess Championship, World Chess Champion. He became the first grandmaster from India in 1988, and is one of the few players to have ...
and Veselin Topalov saw Anand making 13 consecutive knight moves (albeit using both knights); online commentators jested that Anand was trying to solve the knight's tour problem during the game.


Existence

Schwenk proved that for any board with ''m'' ≤ ''n'', a closed knight's tour is always possible ''unless'' one or more of these three conditions are met: # ''m'' and ''n'' are both odd # ''m'' = 1, 2, or 4 # ''m'' = 3 and ''n'' = 4, 6, or 8. Cull ''et al.'' and Conrad ''et al.'' proved that on any rectangular board whose smaller dimension is at least 5, there is a (possibly open) knight's tour.


Number of tours

On an board, there are exactly 26,534,728,821,064 directed closed tours (i.e. two tours along the same path that travel in opposite directions are counted separately, as are rotations and reflections). The number of ''
undirected In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
'' closed tours is half this number, since every tour can be traced in reverse. There are 9,862 undirected closed tours on a board.


Finding tours with computers

There are several ways to find a knight's tour on a given board with a computer. Some of these methods are
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s while others are
heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate ...
s.


Brute-force algorithms

A
brute-force search In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...
for a knight's tour is impractical on all but the smallest boards. For example, there are approximately 4×1051 possible move sequences on an board, and it is well beyond the capacity of modern computers (or networks of computers) to perform operations on such a large set. However, the size of this number is not indicative of the difficulty of the problem, which can be solved "by using human insight and ingenuity ... without much difficulty."


Divide-and-conquer algorithm In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
s

By dividing the board into smaller pieces, constructing tours on each piece, and patching the pieces together, one can construct tours on most rectangular boards in
linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
– that is, in a time proportional to the number of squares on the board.


Warnsdorff's rule

Warnsdorff's rule is a
heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate ...
for finding a single knight's tour. The knight is moved so that it always proceeds to the square from which the knight will have the ''fewest'' onward moves. When calculating the number of onward moves for each candidate square, we do not count moves that revisit any square already visited. It is possible to have two or more choices for which the number of onward moves is equal; there are various methods for breaking such ties, including one devised by Pohl and another by Squirrel and Cull. This rule may also more generally be applied to any graph. In graph-theoretic terms, each move is made to the adjacent vertex with the least degree. Although the
Hamiltonian path problem In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or ...
is
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in
linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. The knight's tour is such a special case. The
heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate ...
was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. von Warnsdorff in 1823. A computer program that finds a knight's tour for any starting position using Warnsdorff's rule was written by Gordon Horsington and published in 1984 in the book ''Century/Acorn User Book of Computer Puzzles''.


Neural network solutions

The knight's tour problem also lends itself to being solved by a
neural network A neural network is a network or circuit of biological neurons, or, in a modern sense, an artificial neural network, composed of artificial neurons or nodes. Thus, a neural network is either a biological neural network, made up of biological ...
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 A neuron, neurone, or nerve cell is an electrically excitable cell that communicates with other cells via specialized connections called synapses. The neuron is the main component of nervous tissue in all animals except sponges and placozoa ...
, 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 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 (those exactly one knight's move away) according to the following transition rules: :: U_ (N_) = U_t(N_) + 2 - \sum_ V_t(N) :: V_ (N_) = \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, either the network encodes a knight's tour or a series of two or more independent circuits within the same board.


See also

* Abu Bakr bin Yahya al-Suli * Eight queens puzzle * George Koltanowski * Longest uncrossed knight's path *
Self-avoiding walk In mathematics, a self-avoiding walk (SAW) is a sequence of moves on a lattice (a lattice path) that does not visit the same point more than once. This is a special case of the graph theoretical notion of a path. A self-avoiding polygon (S ...


Notes


External links

*
H. C. von Warnsdorf 1823 in Google Books
*{{cite journal, doi=10.1109/MPOT.2012.2219651, title=A Generalized Pseudo-Knight?s Tour Algorithm for Encryption of an Image, journal=IEEE Potentials, volume=32, issue=6, pages=10–16, year=2013, last1=Philip, first1=Anish Chess problems Graph algorithms Hamiltonian paths and cycles Mathematical chess problems Mathematical problems