This post has already been read 4962 times!
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.
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]
Let us first discuss the Naive algorithm for this problem and then the Backtracking algorithm.
Naive Algorithm for Knight’s tour
The Naive Algorithm is to generate all tours one by one and check if the generated tour satisfies the constraints.
while there are untried tours { generate the next tour if this tour covers all squares { print this path; } }
Backtracking works in an incremental way to attack problems. Typically, we start from an empty solution vector and one by one add items (Meaning of item varies from problem to problem. In context of Knight’s tour problem, an item is a Knight’s move). When we add an item, we check if adding the current item violates the problem constraint, if it does then we remove the item and try other alternatives. If none of the alternatives work out then we go to previous stage and remove the item added in the previous stage. If we reach the initial stage back then we say that no solution exists. If adding an item doesn’t violate constraints then we recursively add items one by one. If the solution vector becomes complete then we print the solution.
Backtracking Algorithm for Knight’s tour
Following is the Backtracking algorithm for Knight’s tour problem.
If all squares are visited print the solution Else a) Add one of the next moves to solution vector and recursively check if this move leads to a solution. (A Knight can make maximum eight moves. We choose one of the 8 moves in this step). b) If the move chosen in the above step doesn't lead to a solution then remove this move from the solution vector and try other alternative moves. c) If none of the alternatives work then return false (Returning false will remove the previously added item in recursion and if false is returned by the initial call of recursion then "no solution exists" )
Following is C implementation for Knight’s tour problem. It prints one of the possible solutions in 2D matrix form. Basically, the output is a 2D 8*8 matrix with numbers from 0 to 63 and these numbers show steps made by Knight.
Following is C implementation for Knight’s tour problem. It prints one of the possible solutions in 2D matrix form. Basically, the output is a 2D 8*8 matrix with numbers from 0 to 63 and these numbers show steps made by Knight.
Output:
0 59 38 33 30 17 8 63 37 34 31 60 9 62 29 16 58 1 36 39 32 27 18 7 35 48 41 26 61 10 15 28 42 57 2 49 40 23 6 19 47 50 45 54 25 20 11 14 56 43 52 3 22 13 24 5 51 46 55 44 53 4 21 12
Knight Graph
The knight graph is a graph on
vertices in which each vertex represents a square in an
chessboard, and each edge corresponds to a legal move by a knight (which may only make moves which simultaneously shift one square along one axis and two along the other).
The number of edges in the knight graph is
(8 times the triangular numbers), so for
, 2, ..., the first few values are 0, 0, 8, 24, 48, 80, 120, ... (OEIS A033996).
Knight graphs are bipartite and therefore are perfect.
The following table summarizes some named graph complements of knight graphs.
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
The knight graph is implemented in Mathematica as KnightTourGraph[m, n], and precomputed properties are available in using GraphData[
"Knight",
m, n
].
Closed formulas for the numbers of
-graph cycles of the
knight graph are given by
for
odd and
![]() |
![]() |
![]() |
(1)
|
(E. Weisstein, Nov. 16, 2014).
A knight's path is a sequence of moves by a knight such that each square of the board is visited exactly once. It is therefore a Hamiltonian path on the corresponding knight graph. Conrad et al. (1994) shows that a knight's path exists on an board iff
.
more about at : http://mathworld.wolfram.com/KnightGraph.html