TY - JOUR
T1 - Optimal algorithms for constructing knight's tours on arbitrary n×m chessboards
AU - Lin, Shun Shii
AU - Wei, Chung Liang
N1 - Funding Information:
We thank the reviewers for their valuable comments and suggestions. This research was supported in part by a Grant NSC89-2213-E-003-007 from National Science Council, ROC. Our gratitude also goes to the Academic Paper Editing Clinic, National Taiwan Normal University.
PY - 2005/3/15
Y1 - 2005/3/15
N2 - 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×n, an n×(n+1) or an n×(n+2) chessboard in O(n2) (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×m chessboard if such a solution exists. Our algorithms also run in linear time (O(nm)) on a sequential processor.
AB - 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×n, an n×(n+1) or an n×(n+2) chessboard in O(n2) (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×m chessboard if such a solution exists. Our algorithms also run in linear time (O(nm)) on a sequential processor.
KW - Divide-and-conquer algorithm
KW - Knight's tour problem
KW - Optimal algorithm
UR - http://www.scopus.com/inward/record.url?scp=12344288321&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=12344288321&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2004.11.002
DO - 10.1016/j.dam.2004.11.002
M3 - Article
AN - SCOPUS:12344288321
SN - 0166-218X
VL - 146
SP - 219
EP - 232
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 3
ER -