Contents

The first description of a generalized backtrack search algorithm was in [35]. Let us first define a restricted version of the search problem.

TheSearch problem:

Given a collection of sets of candidates and a booleancompatibilityfunction defined for all and , find anm-tuplewith such that is true for all .

For example, if we take and let be the set of all
candidates for column **i** of the incidence matrix of a projective plane,
then can be defined as

A nice way to organize the information inherent in the partial solutions
is the backtrack search tree. Here, the empty partial solution is
taken as the root, and the partial solution is
represented as the child of the partial solution .
Following the computer science terminology, we often called a partial
solution a * node*. It is often true that the computing cost of
processing a node is independent of its level **k**. Under this assumption,
the total computing cost of a search is equal to the number of nodes in
the search tree times the cost of processing a node.

The number of nodes in the search tree can often be reduced by using the

This process of reducing the search tree by using symmetry operations is
called * isomorph rejection*. Two partial solutions are said to be *
isomorphic* if there is a symmetry operation mapping one to the other. To
determine whether a solution exists, it is only necessary to extend the
non-isomorphic partial solutions, because if a partial solution can be
extended to a complete solution, then every other isomorphic partial
solution can also be so extended. The testing of whether two partial
solutions are isomorphic is called * isomorphism testing*. The set of
symmetry operations mapping a partial solution to itself forms an *
automorphism group*. In the context of projective planes, an automorphism
of a complete solution is also called a * collineation*.

The efficient use of the symmetry operations is one of the most difficult
problem in a backtrack search. It is both a blessing and a curse --- a
blessing because there is always hope of further optimization and a curse
because it is the source of many programming errors. However, following
the method of MacWilliams * et al.*, it is clear that the existence
question of the plane of order 10 is headed towards a computer-based
solution and that symmetry consideration is a necessary tool for
efficiency reasons.

In his 1974 Ph. D. thesis, Carter picked up where MacWilliams * et al.*
had left off. He showed that there are six possible starting
configurations associated with a codeword of weight 16. By using the
computer, he managed to eliminate four of the cases, as well as one
subcase of the fifth. He used a total of about 100 hours of computer time,
mostly on a CDC 6600 at the Institute for Defense Analyses (IDA) in
Princeton, New Jersey, and also on a CDC 7600 at the Lawrence Radiation
Laboratories in Berkeley, California. His search investigated about
nodes, or about nodes per second.
This was the situation when we entered the picture. While we knew
, the search for weight 16 codewords was about three-quarter
done and the search for weight 12 codewords was presumed to be too
difficult. The person who suggested the problem to us was John Thompson.

Contents