In addition to the general mapping from one level to the next, there is the problem-specific aspect of the algorithm, namely the choice of phases for the nogood sets at each level. In the ideal case described above, random phases were given to each nogood, resulting in a great deal of cancellation for nogoods at the solution level. While this is a reasonable choice for the unitary mapping, other policies are possible as well. For example, one could simply invert the phase of each nogood (i.e., multiply its amplitude by -1). This choice doesn't work well for the idealized map to supersets only but, as shown below, is helpful for the unitary map. It can be motivated by considering the coefficients shown in Fig. 2. Specifically, when a nogood is encountered for the first time on a path through the lattice, we would like to cancel phase to its supersets but at the same time enhance amplitude in other sets likely to lead to solutions. Because is negative, inverting the phase will tend to add to sets that differ by one element from the nogood. At least some of these will avoid violating the small constraint that produced this nogood set, and hence may contribute eventually to sets that do lead to solutions.

Moreover, one could use information on the sets at the next level to decide what to do with the phase: as currently described, the computation makes no use of testing the consistency of sets at the solution level itself, and hence is completely ineffective for problems where the test requires the complete set. Perhaps better would be to mark a state as nogood if it has no consistent extensions with one more item (this is simple to check since the number of extensions grows only linearly with problem size). Another possibility is for the phase to be adjusted based on how many constraints are violated, which could be particularly appropriate for partial constraint satisfaction problems [21] or other optimization searches.

Wed Mar 20 16:29:17 PST 1996