Backtrack Search using a Computer

Contents Next: The Home Stretch Up: The Beginning of Previous: The Beginning of

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

Search problem:
Given a collection of sets of candidates and a boolean compatibility function defined for all and , find an m-tuple with such that is true for all .

The m-tuple satisfying the above condition is called a solution. The term compatibility was first introduced by Carter in 1974 [9]. This version is restricted because the compatibility function is only defined on ordered pairs rather than on all k-tuples,

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

where

denotes the inner product of columns x and y. A solution is then a complete incidence matrix. [an error occurred while processing this directive] In a backtrack approach, we generate k-tuples with

. A k-tuples

is a partial solution at level k if

is true for all

. The basic idea of the backtrack approach is to extend a partial solution at level k to one at level k+1, and if this extension is impossible, then to go back to the partial solution at level k-1 and attempt to generate a different partial solution at level k.

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. [an error occurred while processing this directive]

The number of nodes in the search tree can often be reduced by using the symmetry or property-preserving operations. If A is the incidence matrix of a projective plane, then the operations of permuting the rows and permuting the columns of A correspond only to reordering the lines and points of the plane. These operations preserve the property of being a projective plane. To see how they reduce the size of a search tree, consider the plane of order 10. There are

choices for the first column, corresponding to the number of ways of placing 11 ones in the 111 rows. By using the row permutations, we can assume that all these ones are placed on the first 11 rows, reducing the number of partial solutions

from

to 1. Mathematicians love to use the phrase ``without loss of generality'' to indicate a simplification by symmetry operations. So without loss of generality, the second column has only one choice --- with a one in the first row and the remaining 10 ones in rows 12 to 21. Now, row 1 has nine remaining ones. By permuting columns, we can assume that these remaining ones of row 1 are in columns 3 to 11. Next, by row permutation, the remaining 10 ones of column 3 can be placed in rows 22 to 31. Continuing in this manner, it is not difficult to show that there is only one choice up to column 21. Beyond this point, symmetry operations are difficult to visualize, because they often involve combinations of row and column permutations.

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. [an error occurred while processing this directive]

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. [an error occurred while processing this directive]

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. [an error occurred while processing this directive] 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 Next: The Home Stretch Up: The Beginning of Previous: The Beginning of