Karla Alwan
ABSTRACT
In this paper we discuss how we developed a highly efficient backtracking algorithm based on proofs we devised concerning Hamiltonian circuits. The algorithm concentrates on a Knight's Tour in which the knight starts and ends on the same square--a Hamiltonian circuit.One version of the program we developed is designed to find all Hamiltonian circuits for any given board. The largest board we exhausted is a six-by-seven. We found 1,067,638 circuits in 43 minutes 2 seconds (actual cpu time), or 413 circuits per second using a Solbourne 4/602.The final version of the program concentrates on finding one Hamiltonian circuit in very large boards. Our software and hardware limit us to a maximum board size of 520x520 in which we found a Hamiltonian circuit in 3 minutes 19 seconds. All of our data from using various sized boards indicate that the program has a time complexity close to O(m.n) on an n-by-m board.
- 1.Ball, W. W. Rouse, Mathematical Recreations and Essays, The MacMillan Company, New York 1947, pp 174-185.Google Scholar
- Finding re-entrant knight's tours on n-by-m boards
Recommendations
A method for finding Hamilton paths and Knight's tours
The use of Warnsdorff's rule for finding a knight's tour is generalized and applied to the problem of finding a Hamilton path in a graph. A graph-theoretic justification for the method is given.
Generalized knight's tours on rectangular chessboards
In [Math. Mag. 64 (1991) 325-332], Schwenk has completely determined the set of all integers m and n for which the mxn chessboard admits a closed knight's tour. In this paper, (i) we consider the corresponding problem with the knight's move generalized ...
Optimal algorithms for constructing knight's tours on arbitrary n×m chessboards
The knight's tour problem is an ancient puzzle whose goal is to find out how to construct a series of legal moves made by a knight so that it visits every square of a chessboard exactly once. In previous works, researchers have partially solved this ...
Comments