Reducing the search space

For a class I'm taking, we're looking at Constraint Satisfaction Problems or CSPs. For a homework assignment we're looking at different methods of solving these CSPs. One way to do this is to create a tree of the possible variables in the CSP and at each level assign values. One obvious optimization is to reduce the assigned values at each level to only those that meet the constraints. According to the text this reduces the search space from n!*d^n to d^n where d is the size of the domain and n is the number of variables in the CSP.

As much as I'm interested in theory, practice is very helpful in explanation. One problem is the following:

  TWO
+ TWO
------
  FOUR

This is a crypt-arithmetic puzzle where a unique value is assigned to each letter, and no word can have leading 0's. To see this for myself I quickly implemented this in ruby to see the difference between constraining the search at each level and not. Results?

Unconstrained search (should be n!*d^n):

real 0m44.690s
user 0m42.769s
sys  0m0.315s

Constrained Search (should be reduced to d^n)

real 0m0.049s
user 0m0.037s
sys  0m0.005s

As you can see, a huge difference. Even though I fully understood the math, I was surprised how much of a difference it made by reducing the search space (even though it involved more checks at each level).

In summary... reduce