A general backtrack algorithm that eliminates most redundant tests

Experimental measurements (figure 1) reveal reduction by a factor of 2.5 for the 8-queens puzzle (factor of 8.7 for 16 queens) in T, the number of pair-tests performed before finding a solution (i.e., first solution). " seconds, net speedup is by a factor of 2.0 and 6.0 for 8-and 16-queens, respectively. The speedup can be attributed to the elimination of almost all redundant tests otherwise recomputed in many parts of the search tree, as indicated in figure 2, which shows the mean number of times, D, an arbitrary pair-test is executed. If D 1 then all tests are distinct (no recomputatiOn). Note that each data point in the figures represents the mean over 30 or 70 problem instances that differ as follows: instead of instantiating queen 3, say, on square (3,1), then on (3,2),..., then (3,8), these 8 squares are ordered randomly.