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 -