Editing Knight's tour

{{Short description|Mathematical problem set on a chessboard}}
[[File:Knight's tour anim 2.gif|right|thumb|250px|An open knight's tour of a chessboard]]
[[File:Knights-Tour-Animation.gif|right|thumb|250px|An animation of an open knight's tour on a 5 × 5 board]]
A '''knight's tour''' is a sequence of moves of a [[knight (chess)|knight]] on a [[chessboard]] 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".<ref>{{cite thesis |last1=Brown |first1=Alfred James |title=Knight's Tours and Zeta Functions |type=MS thesis |publisher=San José State University |date=2017 |doi=10.31979/etd.e7ra-46ny |url=https://scholarworks.sjsu.edu/etd_theses/4836/ |page=3|doi-access=free }}</ref><ref>{{cite book |last1=Hooper |first1=David |authorlink1=David Vincent Hooper |last2=Whyld |first2=Kenneth |authorlink2=Kenneth Whyld |title=The Oxford Companion to Chess |publisher=[[Oxford University Press]] |edition=2nd |year=1996 |orig-year=First pub. 1992 |contribution=knight's tour |page=204 |isbn=0-19-280049-3|title-link=The Oxford Companion to Chess }}</ref>

The '''knight's tour problem''' is the [[mathematical chess problem|mathematical problem]] of finding a knight's tour. Creating a [[computer program|program]] to find a knight's tour is a common problem given to [[computer science]] students.<ref>{{cite book |first1=H. M.|last1=Deitel|first2=P. J.|last2=Deitel|title=Java How To Program Fifth Edition.|publisher=[[Prentice Hall]]|isbn=978-0131016217|edition=5th|pages=[https://archive.org/details/javahowtoprogram00deit_1/page/326 326–328]|date=2003|url-access=registration|url=https://archive.org/details/javahowtoprogram00deit_1/page/326}}</ref> Variations of the knight's tour problem involve chessboards of different sizes than the usual {{nowrap|8 × 8}}, as well as irregular (non-rectangular) boards.

==Theory==
[[File:Knight's graph showing number of possible moves.svg|left|thumb|270px|[[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]].<ref name=Conrad1994>{{cite journal |first1=A. |last1=Conrad |first2=T. |last2=Hindrichs |first3=H. |last3=Morsy |name-list-style=amp |first4=I. |last4=Wegener |title=Solution of the Knight's Hamiltonian Path Problem on Chessboards |journal=Discrete Applied Mathematics |volume=50 |issue=2 |pages=125–134 |year=1994 |doi=10.1016/0166-218X(92)00170-Q|doi-access=free }}</ref>
{{Clear}}

==History==
[[File:Turk-knights-tour.svg|right|thumb|250px|The knight's tour as solved by [[Mechanical Turk|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 [[Rudrata]]'s {{lang|sa-Latn|Kavyalankara}}<ref>
{{cite book
|author = Satyadev, Chaudhary
|title = Kavyalankara of Rudrata (Sanskrit text, with Hindi translation);
|publisher = Parimal Sanskrit Series No. 30
|location = Delhitraversal
|title-link = Rudrata#Kavyalankara
}}
</ref> (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 ({{lang|sa-Latn|citra-alaṅkāra}}) called the {{lang|sa-Latn|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|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:

{| style="border:0; text-align:center;"
|-
|से||ना||ली||ली||ली||ना||ना||ली
|-
|ली||ना||ना||ना||ना||ली||ली||ली
|-
|न||ली||ना||ली||ले||ना||ली||ना
|-
|ली||ली||ली||ना||ना||ना||ना||ली
|}

transliterated:
{| style="border:0; text-align:center;"
|-
|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 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 Vaishnavism|Sri Vaishnava]] poet and philosopher [[Vedanta Desika]], during the 14th century, in his 1,008-verse magnum opus praising the deity [[Ranganatha]]'s divine sandals of [[Ranganathaswamy Temple, Srirangam|Srirangam]], [[Paduka Sahasra]]m (in chapter 30: ''Chitra Paddhati'') has composed two consecutive [[Sanskrit]] verses containing 32 letters each (in [[Anuṣṭubh|Anushtubh]] meter) where the second verse can be derived from the first verse by performing a Knight's tour on a {{nowrap|4 × 8}} board, starting from the top-left corner.<ref>{{cite web |url=https://www.iiitb.ac.in/CSL/projects/paduka/paduka.html|title=Indian Institute of Information Technology, Bangalore|website=www.iiitb.ac.in|access-date=2019-10-11}}</ref> The transliterated 19th verse is as follows:
{| class="wikitable"
|sThi
<small>(1)</small>
|rA
<small>(30)</small>
|ga
<small>(9)</small>
|sAm
<small>(20)</small>
|sa
<small>(3)</small>
|dhA
<small>(24)</small>
|rA
<small>(11)</small>
|dhyA
<small>(26)</small>
|-
|vi
<small>(16)</small>
|ha
<small>(19)</small>
|thA
<small>(2)</small>
|ka
<small>(29)</small>
|tha
<small>(10)</small>
|thA
<small>(27)</small>
|ma
<small>(4)</small>
|thA
<small>(23)</small>
|-
|sa
<small>(31)</small>
|thpA
<small>(8)</small>
|dhu
<small>(17)</small>
|kE
<small>(14)</small>
|sa
<small>(21)</small>
|rA
<small>(6)</small>
|sA
<small>(25)</small>
|mA
<small>(12)</small>
|-
|ran
<small>(18)</small>
|ga
<small>(15)</small>
|rA
<small>(32)</small>
|ja
<small>(7)</small>
|pa
<small>(28)</small>
|dha
<small>(13)</small>
|nna
<small>(22)</small>
|ya
<small>(5)</small>
|}
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.<ref>{{cite web |url=http://bridge-india.blogspot.com/2011/08/paduka-sahasram-by-vedanta-desika.html|title=Bridge-India: Paduka Sahasram by Vedanta Desika|last=Bridge-india|date=2011-08-05|website=Bridge-India|access-date=2019-10-16}}</ref>

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.<ref>[[A History of Chess]] by Murray</ref> Nilakantha's work is an extraordinary achievement being a fully symmetric closed tour, predating the work of Euler (1759) by at least 60 years.

[[File:Euler knight tour semimagic square.svg|thumb|A [[semimagic square]] (its diagonals do not sum to its [[magic constant]], 260) also forming a knight's tour &ndash; no fully magic tours exist on an 8x8 board (although they do exist on larger boards)<ref>{{cite web | url=http://mathworld.wolfram.com/news/2003-08-06/magictours/ | title=MathWorld News: There Are No Magic Knight's Tours on the Chessboard }}</ref>]]
After Nilakantha, one of the first mathematicians to investigate the knight's tour was [[Leonhard Euler]]. 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]] 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 ''[[Life a User's Manual]]''.

The sixth game of the [[World Chess Championship 2010]] between [[Viswanathan Anand]] 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==
[[File:Thomasson symmetric closed knights tour.svg|thumb|A radially symmetric closed knight's tour]]
Schwenk<ref>{{cite journal
|author= Allen J. Schwenk
|title= Which Rectangular Chessboards Have a Knight's Tour?
|journal= Mathematics Magazine
|year= 1991
|volume= 64
|issue= 5
|pages= 325–332
|doi= 10.1080/0025570X.1991.11977627
|s2cid= 28726833
|url= https://pdfs.semanticscholar.org/c3f5/e69e771771de1be50a8a8bf2561804026d69.pdf
|archive-url= https://web.archive.org/web/20190526154119/https://pdfs.semanticscholar.org/c3f5/e69e771771de1be50a8a8bf2561804026d69.pdf
|url-status= dead
|archive-date= 2019-05-26
}}</ref> proved that for any {{nowrap|''m'' × ''n''}} 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.<ref name=Conrad1994/><ref name=Cull1978/> For any {{nowrap|''m'' × ''n''}} board with ''m'' ≤ ''n'', a (possibly open) knight's tour is always possible ''unless'' one or more of these three conditions are met: 
# ''m'' = 1 or 2
# ''m'' = 3 and ''n'' = 3, 5, or 6<ref>{{cite web | url=https://www.mayhematics.com/t/oa.htm | title=Knight's Tours on 3 by N Boards }}</ref>
# ''m'' = 4 and ''n'' = 4.<ref>{{cite web | url=https://www.mayhematics.com/t/oc.htm | title=Knight's Tours on 4 by N Boards }}</ref>

==Number of tours==
On an {{nowrap|8 × 8}} board, there are exactly 26,534,728,821,064 [[Glossary of graph theory#D|directed]] closed tours (i.e. two tours along the same path that travel in opposite directions are counted separately, as are [[rotation (mathematics)|rotations]] and [[reflection (mathematics)|reflections]]).<ref name=lw96>{{cite journal
 | last1 = Löbbing | first1 = Martin
 | last2 = Wegener | first2 = Ingo
 | doi = 10.37236/1229
 | issue = 1
 | journal = Electronic Journal of Combinatorics
 | mr = 1368332
 | at = Research Paper 5
 | title = The number of knight's tours equals 33,439,123,484,294—counting with binary decision diagrams
 | volume = 3
 | year = 1996}} See attached comment by Brendan McKay, Feb 18, 1997, for the corrected count.</ref><ref>{{cite journal
|authorlink= Brendan McKay (mathematician)
|author= Brendan McKay
|title= Knight's Tours on an {{nowrap|8 × 8}} Chessboard
|journal= Technical Report TR-CS-97-03
|publisher= Department of Computer Science, Australian National University
|year= 1997
|url= http://www.combinatorics.org/ojs/index.php/eljc/article/downloadSuppFile/v3i1r5/mckay
|access-date= 2013-09-22
|archive-url= https://web.archive.org/web/20130928001649/http://www.combinatorics.org/ojs/index.php/eljc/article/downloadSuppFile/v3i1r5/mckay
|archive-date= 2013-09-28
|url-status= dead
}}</ref><ref>{{cite book
|author= Wegener, I.
|title= Branching Programs and Binary Decision Diagrams
|publisher= Society for Industrial & Applied Mathematics
|year= 2000
|isbn= 978-0-89871-458-6
|url= https://books.google.com/books?id=-DZjVz9E4f8C&dq=532&pg=PA369}}</ref> The number of ''[[Glossary of graph theory#D|undirected]]'' closed tours is half this number, since every tour can be traced in reverse. There are 9,862 undirected closed tours on a {{nowrap|6 × 6}} board.<ref>{{MathWorld|urlname=KnightGraph|title=Knight Graph}}</ref>
{| class=wikitable style="margin-left: 4em; text-align: right;"
! ''n'' !! Number of directed tours (open and closed)<br/>on an ''n'' × ''n'' board<br/>{{OEIS|A165134}}
|-
| 1 || 1
|-
| 2 || 0
|-
| 3 || 0
|-
| 4 || 0
|-
| 5 || 1,728
|-
| 6 || 6,637,920
|-
| 7 || 165,575,218,320
|-
| 8 || 19,591,828,170,979,904
|}

==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]]s, while others are [[heuristic]]s.

===Brute-force algorithms===
A [[brute-force search]] for a knight's tour is impractical on all but the smallest boards.<ref name=Simon01a>{{citation|title=Evolutionary Optimization Algorithms|first=Dan|last=Simon|publisher=John Wiley & Sons|year=2013|isbn=9781118659502|pages=449–450|url=https://books.google.com/books?id=gwUwIEPqk30C&pg=PA449|quote=The knight's tour problem is a classic combinatorial optimization problem. ... The cardinality ''N<sub>x</sub>'' of ''x'' (the size of the search space) is over 3.3×10<sup>13</sup> (Löbbing and Wegener, 1995). We would not want to try to solve this problem using brute force, but by using human insight and ingenuity we can solve the knight's tour without much difficulty. We see that the cardinality of a combinatorial optimization problem is not necessarily indicative of its difficulty.}}</ref> On an {{nowrap|8 × 8}} board, for instance, there are {{val|13,267,364,410,532|fmt=commas}} knight's tours,<ref name=lw96/> and a much greater number of sequences of knight moves of the same length. 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."<ref name=Simon01a/>

===[[Divide-and-conquer algorithm]]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 [[time complexity#Linear time|linear time]] – that is, in a time proportional to the number of squares on the board.<ref name=Cull1978>{{cite journal|last= Cull|first= P.|author2=De Curtins, J.|title= Knight's Tour Revisited|journal= Fibonacci Quarterly|volume= 16|year= 1978|issue= 3|pages= 276–285 |doi= 10.1080/00150517.1978.12430328|url=https://www.fq.math.ca/Scanned/16-3/cull.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.fq.math.ca/Scanned/16-3/cull.pdf |archive-date=2022-10-09 |url-status=live}}</ref><ref>{{cite journal|last= Parberry|first= Ian|title= An Efficient Algorithm for the Knight's Tour Problem|journal= Discrete Applied Mathematics|volume= 73|issue= 3|year= 1997|pages= 251–260|doi=10.1016/S0166-218X(96)00010-8 |url=https://core.ac.uk/download/pdf/81964499.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://core.ac.uk/download/pdf/81964499.pdf |archive-date=2022-10-09 |url-status=live|doi-access= free}}</ref>

===Warnsdorf's rule===
{{Chess diagram
| tright
|
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|x3|  |x7|  |  |  |  |
|  |  |  |x7|  |  |  |
|  |nl|  |  |  |  |  |
|  |  |  |x7|  |  |  |
|x2|  |x5|  |  |  |  |
|  |  |  |  |  |  |  |
|A graphical representation of Warnsdorf's Rule. Each square contains an integer giving the number of moves that the knight could make from that square. In this case, the rule tells us to move to the square with the smallest integer in it, namely 2.
}}

[[File:Knight's Tour of 130x130 Square Board.png|thumb|A very large (130 × 130) square open knight's tour created using Warnsdorf's Rule]]

Warnsdorf's rule is a [[heuristic]] 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<ref name="pohl"/> and another by Squirrel and Cull.<ref>{{cite web |url=https://github.com/douglassquirrel/warnsdorff/blob/master/5_Squirrel96.pdf?raw=true |title=A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards |access-date=2011-08-21 |last=Squirrel |first=Douglas |author2=Cull, P. |website=[[GitHub]] |year=1996}}</ref>

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 (graph theory)|degree]].<ref name="Van Horn et. al">{{cite conference| first=Gijs| last=Van Horn| author2=Olij, Richard| author3=Sleegers, Joeri| author4=Van den Berg, Daan| title=A Predictive Data Analytic for the Hardness of Hamiltonian Cycle Problem Instances| conference=DATA ANALYTICS 2018: The Seventh International Conference on Data Analytics| publisher=[[Xpert Publishing Services|XPS]]| location=Athens, greece| pages=91–96| year=2018| url=https://pure.uva.nl/ws/files/30312375/_2018_Van_Horn_et_al_A_Predictive_Data_Analytic.pdf| access-date=2018-11-27| isbn=978-1-61208-681-1}}</ref> Although the [[Hamiltonian path problem]] is [[NP-hardness|NP-hard]] in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in [[linear time]].<ref name="pohl">{{cite journal|last= Pohl|first= Ira|title= A method for finding Hamilton paths and Knight's tours|journal= Communications of the ACM|volume= 10|issue= 7|date= July 1967|pages= 446–449|doi= 10.1145/363427.363463|citeseerx= 10.1.1.412.8410|s2cid= 14100648}}</ref> The knight's tour is such a special case.<ref name="alwan-waters">{{cite conference| first=Karla |last=Alwan|author2=Waters, K. |title=Finding Re-entrant Knight's Tours on N-by-M Boards|conference=ACM Southeast Regional Conference| publisher=[[Association for Computing Machinery|ACM]]| location=New York, New York| pages=377–382| year=1992| doi= 10.1145/503720.503806}}</ref>

The [[heuristic]] was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. von Warnsdorf in 1823.<ref name="alwan-waters"/>

A computer program that finds a knight's tour for any starting position using Warnsdorf's rule was written by Gordon Horsington and published in 1984 in the book ''Century/Acorn User Book of Computer Puzzles''.<ref>{{cite book |title=Century/Acorn User Book of Computer Puzzles|editor-first=Simon|editor-last=Dally|isbn=978-0712605410|year=1984|publisher=Century Communications }}</ref>

===Neural network solutions===
[[File:Knight's Tour 24x24.svg|right|thumb|250px|Closed knight's tour on a {{nowrap|24 × 24}} board solved by a neural network]]
The knight's tour problem also lends itself to being solved by a [[Artificial neural network|neural network]] implementation.<ref>Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." ''Neurocomputing'', 4(5):249–254, 1992.</ref> The network is set up such that every legal knight's move is represented by a [[artificial neuron|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 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:
::<math display="block">
U_{t+1} (N_{i,j}) = U_t(N_{i,j}) + 2 - \sum_{N \in G(N_{i,j})} V_t(N)
</math>

::<math display="block">
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.
</math>

where <math>t</math> represents discrete intervals of time, <math>U(N_{i,j})</math> is the state of the neuron connecting square <math>i</math> to square <math>j</math>, <math>V(N_{i,j})</math> is the output of the neuron from <math>i</math> to <math>j</math>, and <math>G(N_{i,j})</math> 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 <math>t</math> to <math>t+1</math>. 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]]

==Notes==
{{Reflist|30em}}

==External links==
*{{Commons category-inline|Knight's Tours}}
*{{OEIS el|1=A001230|2=Number of undirected closed knight's tours on a 2n X 2n chessboard}}
*[https://books.google.com/books?id=w5FZAAAAYAAJ&q=h.+c.+von+warnsdorf H. C. von Warnsdorf 1823 in Google Books]
*[http://www.mayhematics.com/t/1n.htm Introduction to Knight's tours by George Jelliss]
*[http://www.mayhematics.com/t/t.htm Knight Tour Notes by George Jelliss]
*{{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|s2cid=39213422 }}

[[Category:Chess problems]]
[[Category:Graph algorithms]]
[[Category:Hamiltonian paths and cycles]]
[[Category:Mathematical chess problems]]
[[Category:Mathematical problems]]