Optimal algorithms for constructing knight's tours on arbitrary n×m chessboards

Shun Shii Lin, Chung Liang Wei

研究成果: 雜誌貢獻文章同行評審

18 引文 斯高帕斯(Scopus)

摘要

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.

原文英語
頁(從 - 到)219-232
頁數14
期刊Discrete Applied Mathematics
146
發行號3
DOIs
出版狀態已發佈 - 2005 三月 15

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

指紋 深入研究「Optimal algorithms for constructing knight's tours on arbitrary n×m chessboards」主題。共同形成了獨特的指紋。

引用此