Knight 39;s Tour Puzzle Solution
Marilina Crawn
A knight's tour is a sequence of moves of a 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.[1][2]
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.[3] Variations of the knight's tour problem involve chessboards of different sizes than the usual 8 8, as well as irregular (non-rectangular) boards.
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.[4]
The earliest known reference to the knight's tour problem dates back to the 9th century AD. In Rudrata's Kavyalankara[5] (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 chessboard. Rudrata's example is as follows:
The 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 Srirangam, Paduka Sahasram (in chapter 30: Chitra Paddhati) has composed two consecutive Sanskrit 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 4 8 board, starting from the top-left corner.[6] The transliterated 19th verse is as follows:
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.[8] 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. 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 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.
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).[14][15][16] 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.[17]
A brute-force search for a knight's tour is impractical on all but the smallest boards.[18] On an 8 8 board, for instance, there are 13267364410532 knight's tours,[14] 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."[18]
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[20] and another by Squirrel and Cull.[21]
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.[22] 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.[20] The knight's tour is such a special case.[23]
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.[24]
The knight's tour problem also lends itself to being solved by a neural network implementation.[25] 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 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:
Although divergent cases are possible, the network should eventually converge, which occurs when no neuron changes its state from time t \displaystyle t to t + 1 \displaystyle 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.
How can your knight help you during a game if it's not truly acquainted with the chessboard? Make sure you give your knight a tour around the chessboard, so it gets to know the whole battlefield before you start another game.
The knight's tour is a chess problem that first appeared in around the ninth century. It consists of a knight starting at any square of the board and moving to the remaining 63 squares without ever jumping to the same square more than once.
Closed knight's tours are those in which the knight's last move is one knight's move away from the initial position. In practice, this means that the knight's path forms a loop. In this type of tour, the knight can always go through the same path, wherever its starting square is.
Open knight's tours are those in which the knight can't reach its starting square from its final position. The knight can't go through the same path when placed on different starting positions in this type of tour.
A well-known open tour was created in 1847 by William Beverley and published in The Philosophical Magazine in 1848. Beverley's solution is famous for combining the knight's tour features with those of the mathematical concept of a magic square. Assigning a value to each square (determined by the knight's move order) and adding the numbers on each column and each row together always result in 260.
Trying to solve the knight's tour problem is easy on Chess.com. You can do it by going to Chess.com/analysis, choosing the Setup option, and clicking the trashcan icon to clear the board. After that, you can place a knight on any square and try to solve the knight's tour.
You now know what the knight's tour problem is, why you should try to solve it, and how you can do it on Chess.com. Head over to our Lessons page to learn about knight endgames so you can get even better at using your knights to win more games!
Wikipediaquotes several sources for a count of 26,534,728,821,064 for the numberof closed directed tours of the 8x8 board. As Brian Towers notesin his answer, that is equivalent to the count of Knight's toursstarting from some given square (such as a1) and ending on the same square.The same Wikipedia page exhibits several such tours.
If you stop and think about it for a moment you will realise that if the knight starts on a1, moves through all the other squares exactly once before returning to a1 then that sequence of moves constitutes an answer for every square on the board. Hence every solution where the knight returns to the same square is a solution for every square of the board. This was also pointed out by Aric in his answer above.
The function dfns.kt finds a (possibly open) Knight's tour, where the right argument is the board's dimensions, and the optional left argument is the number of solutions to find. Giving -1 on the left causes the function to search all possible solutions.
Since this is a code-golf, this is built to be shorter in code, as opposed to faster in execution. Note that if you want solutions that will run in practical amounts of time, that almost requires some kind of dynamic programming, using a hash in addition to a list, and probably even some kind of heuristic. Otherwise, an exhaustive backtracking search may potentially take a very long time. It would be interesting to see a separate contest for the fastest knight's tour finder for all mxn boards for m0
It works by randomly reordering a list of all coordinates until it gets the right answer. If it takes more than 9*10^99 loops, it assumes that there is no answer. (It will be right the vast majority of the time, since the probability of getting the right order is roughly 1 in 6*10^63).
c80f0f1006