Backtrack searching in the presence of symmetry

Methods from computational group theory are used to improve the speed of backtrack searching on problems with symmetry. The symmetry testing algorithm, which is similar to a color automorphism algorithm, takes the symmetry group as input and uses it to avoid searching equivalent portions of the search space. The algorithm permits dynamic search rearrangement in conjunction with symmetry testing. Experimental results confirm that the algorithm saves a considerable amount of time on some search problems.