Finding re-entrant knight's tours on n-by-m boards
Karla Alwan, Kelly Waters · 1992
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.