Generating Knight's Tours Without Backtracking from Errors.

摘要

We describe research on the problem of generating multiple closed tours of an mxn chessboard by a knight, subject to the constraint that the search scheme used to solve the problem is non-backtracking; i.e., that the search engine never visits a node in the search tree that will ultimately lead to a dead end. We describe our experiences and results in the context of KTC, a search program developed to undertake this task. We describe the implementation of KTC, the search constraints we discovered, and KTC's performance to date, illustrating that a limited amount of domain knowledge can lead to near-perfect search on this class of Hamiltonian circuit construction problems. We close by suggesting promising directions for achieving a perfect search on this problem and the implications of such an achievement.