World Library  
Flag as Inappropriate
Email this Article

Knight's tour

Article Id: WHEBN0000038501
Reproduction Date:

Title: Knight's tour  
Author: World Heritage Encyclopedia
Language: English
Subject: Graph theory, Oulipo, Strategy games, Knight (chess), Chess problem
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Knight's tour

An open knight's tour of a chessboard
An animation of a knight's tour on a 5 by 5 board.

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only 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, otherwise it is open.

The knight's tour problem is the mathematical problem of finding a knight's tour. Creating a program to find a knight's tour is a common problem given to computer science students.[1] Variations of the knight's tour problem involve chessboards of different sizes than the usual 8 × 8, as well as irregular (non-rectangular) boards.

Theory

Knight's graph showing all possible paths for a knight's tour on a standard 8×8 chessboard. The numbers on each node indicate the number of possible moves that can be made from that position.

The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight's tour is similarly an instance of the Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight's tour problem can be solved in linear time.[2]

History

The knight's tour as solved by the Turk, a chess-playing machine hoax. This particular solution is closed (circular), and can thus be completed from any point on the board.

The earliest known reference to the knight's tour problem dates back to the 9th century AD. In Rudraṭa's Kavyalankara[3] (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 ("citra-alaṅkāra") called the "turagapadabandha" 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 chess board. Rudrata's example is as follows:

से ना ली ली ली ना ना ना ली

ली ना ना ना ना ली ली ली ली

न ली ना ली ली ले ना ली ना

ली ली ली ना ना ना ना ना ली

se nā lī lī lī nā nā lī

lī nā nā nā nā lī lī lī

na lī nā lī le nā lī nā

lī lī lī nā nā nā nā lī

For example, the first line can be read from left to right or by moving from the first square to 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.

One of the first mathematicians to investigate the knight's tour was Leonhard Euler. The first procedure for completing the Knight's Tour was Warnsdorff's rule, first described in 1823 by H. C. von Warnsdorff.

In the 20th century, the Life: A User's Manual. The sixth game of the 2010 World Chess Championship between Viswanathan Anand and Veselin Topalov saw Anand making 13 consecutive knight moves (albeit using both knights) -– online commentors jested that Anand was trying to solve the Knight's Tour problem during the game.

Existence

Schwenk[4] proved that for any m × n board with mn, a closed knight's tour is always possible unless one or more of these three conditions are met:

  1. m and n are both odd
  2. m = 1, 2, or 4
  3. 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.[5][2]

Number of tours

On an 8 × 8 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).[6][7][8] The number of undirected closed tours is half this number, since every tour can be traced in reverse. There are 9,862 undirected closed tours on a 6 × 6 board.[9]

The number of directed open tours on an n\times n board for n = 1, 2, … are:

1, 0, 0, 0, 1728, 6637920, 165575218320, 19591828170979904. (sequence A165134 in OEIS).

Finding tours with computers

There are quite a number of ways to find a knight's tour on a given board with a computer. Some of these methods are algorithms while others are heuristics.

Brute force algorithms

A brute-force search for a knight's tour is impractical on all but the smallest boards; for example, on an 8x8 board there are approximately 4×1051 possible move sequences,[10] and it is well beyond the capacity of modern computers (or networks of computers) to perform operations on such a large set.

Divide and conquer algorithms

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 polynomial time.[5][11]

Neural network solutions

Closed knight's tour on a 24 × 24 board solved by a neural network.

The Knight's Tour problem also lends itself to being solved by a neural network implementation.[12] 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 (those exactly one knight's move away) 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, either the network encodes a knight's tour or a series of two or more independent circuits within the same board.

Warnsdorff's rule

a b c d e f g h
8
a6 three
c6 seven
d5 seven
b4 white knight
d3 seven
a2 two
c2 five
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h

Warnsdorff's rule is a heuristic for finding a knight's tour. We move the knight so that we always proceed 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, of course, 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 [13] and another by Squirrel and Cull.[14]

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 is NP-hard in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in linear time.[13] The knight's tour is a special case.[15]

The heuristic was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. von Warnsdorff in 1823.[15] A computer program that finds a Knight's Tour for any starting position using Warnsdorff's rule can be found in the book 'Century/Acorn User Book of Computer Puzzles' edited by Simon Dally (ISBN 071260541X).

See also

Notes

  1. ^ H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." Prentice Hall, Upper Saddle River, New Jersey, pp. 326–328. 2003.
  2. ^ a b Conrad, A.; Hindrichs, T.; Morsy, H. & Wegener, I. (1994). "Solution of the Knight's Hamiltonian Path Problem on Chessboards". Discrete Applied Mathematics 50 (2): 125–134.  
  3. ^ Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with  
  4. ^ Allen J. Schwenk (1991). "Which Rectangular Chessboards Have a Knight’s Tour?". Mathematics Magazine: 325–332. 
  5. ^ a b Cull, P.; De Curtins, J. (1978). "Knight's Tour Revisited". Fibonacci Quarterly 16: 276–285. 
  6. ^ Martin Loebbing; Ingo Wegener (1996). "The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams". The Electronic Journal of Combinatorics 3 (1): R5.  Remark: The authors later admitted that the announced number is incorrect. According to McKay's report, the correct number is 13,267,364,410,532 and this number is repeated in Wegener's 2000 book.
  7. ^  
  8. ^ Wegener, I. (2000). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics.  
  9. ^ Weisstein, Eric W., "Knight's Tour", MathWorld.
  10. ^ "Enumerating the Knight's Tour". 
  11. ^ Parberry, Ian (1997). "An Efficient Algorithm for the Knight's Tour Problem". Discrete Applied Mathematics 73: 251–260.  
  12. ^ Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.
  13. ^ a b Pohl, Ira (July 1967). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM 10 (7): 446–449.  
  14. ^ Squirrel, Douglas; Cull, P. (1996). "A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards". Retrieved 2011-08-21. 
  15. ^ a b Alwan, Karla; Waters, K. (1992). "Finding Re-entrant Knight's Tours on N-by-M Boards" ( 

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.