The knight’s tour problem is as follows: starting with a knight on a square of a chessboard, find a sequence of legal moves that will cause the knight to visit each square exactly once, finally returning to the initial square. Such a problem, in graph theoretic terms, is a restriction of the intractable problem of finding a Hamiltonian circuit, that is, a circuit that visits each node of the graph exactly once.

The authors focus on an even more difficult problem, namely generating the entire set of possible knight’s tours with the additional constraint that the search scheme does not make use of backtracking (no backtracking from failure, or NBFF). In other words, the algorithm is not allowed to visit a node in the search tree that will lead to a dead end.

After a general discussion of the problem, the authors describe the search constraints they developed and the search strategy they chose. They then discuss the experimental results obtained with KTC, a search program developed for this task. Finally, they summarize the performance of KTC and state some conjectures for future work.

Interesting results obtained by the authors are the following. The application of search constraints deriving from even a simple domain’s knowledge can reduce the search space dramatically. Adding more complex knowledge increases the search time with respect to the above case only marginally; thus, it is possible to use sophisticated rules for NBFF without paying too much in terms of increased search time. On the other hand, finding new rules seems to require some supporting mechanisms, such as automated theorem proving.

The proposed approach may be applicable to other intractable problems. The paper is interesting and clearly written, and does not require a deep knowledge of the field.