Generating Knight's Tours Without Backtracking from Errors
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 21, 1993
- Accession Number
- ADA266807
Entities
People
- Hans J. Berliner
- Jefferey A. Shufelt
Organizations
- Carnegie Mellon University