On Backtracking: A Combinatorial Description of the Algorithm

A basic algorithm for solving many discrete problems is the so-called “backtracking” algorithm. The basic problem is that of generating the elements of a subset S₀ of a finite set in an efficient manner. If a group G acts on S₀, then one might wish to obtain only nonisomorphic elements of S₀. In this paper the basic backtracking algorithm is described in terms of chains of partitions on the set S. The corresponding isomorph rejection problem is described in terms of G-invariant chains of partitions on S. Examples and flow charts are given.