[[alternative]]Optimal Algorithms for Constructing Knight's Tours on Rectangular Chessboards

[[abstract]]The knight's tour problem has been studied for a very long period of time. The main purpose of the knight's tour problem is to find out how to construct a series of moves made by a knight visiting every square of a chessboard exactly once. In 1992, Takefuji and Lee state that they are unsure whether the problem of finding a knight's tour is NP-complete. In previous works, all researchers partially solve this problem by offering algorithms for a partial subset of chessboards. For example, among the prior studies, Ian Parberry proposes 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) time on a sequential processor. In this paper, we completely solve this problem and answer the question of Takefuji and Lee by presenting a new method that can construct a closed knight's tour or an open knight's tour on an arbitrary n m chessboard if they exist. Our algorithm runs in linear time (O(nm)) on a sequential processor.