Optimal algorithms for constructing knight's tours on arbitrary nxm 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 problem by offering algorithms for subsets of chessboards. For example, among prior studies, Parberry proposed a divided-and-conquer algorithm that can build a closed knight's tour on an n x n, an n x (n + 1) or an n x (n + 2) chessboard in O(n(2)) (i.e.. linear in area) time on a sequential processor. In this paper we completely solve this problem by presenting new methods that can construct a closed knight's tour or an open knight's tour on an arbitrary n x in chessboard if such a solution exists. Our algorithms also run in linear time (O(nm)) on a sequential processor. (C) 2004 Elsevier B.V. All rights reserved.