Yup pure laziness as it was a toy problem. Though in my experiments with a gecode sudoku model its propagation was amazing, reducing the search space to a handful of branches. Another toy problem of course but one of a significantly larger size. Am I over estimating the power of propagation?
Propagation power really depends on the problem. For some problems, propagation is amazingly good, and for some it does not do much at all.
One can characterize propagation algorithms for the amount of propagation they do. A domain consistent propagation algorithm will make all deductions that are possible to make in a certain state, removing all values for variables that are not a part of any solution to that constraint. Loosely, a bounds consistent propagation algorithm will do the same, but only for the bounds of the variables.
The constraint used in Sudoku (called all_different or distinct) has really good propagation algorithms (both bounds and domain consistent), and is one of the cornerstones of constraint programming.
No, you're not overestimating it but it very much depends on the problem and constraints. It's good to do the d^n search space check to give you a feel for the starting size of the problem but if your problem is heavily constrained i.e. the constraints make finding a solution hard, then propagation is very powerful.
Consider variables a[1:1000] and b[1:10] and constraint a + b = 10. A good solver will use propagation to reduce that to a[1:9] and b[1:9] because there is no support for a >= 10 or b >= 10. Even reducing one extra value from a variable's domain is reducing the search space by a factor so propagation over tight constraints is extremely powerful.
Most arithmetic constraints like those used in your program will use bounds consistency (find support for the lower and upper bound values). Special constraints such as "all different" have their own propagation algorithms that efficiently remove potential values from the domains of multiple variables. These are known as Global Constraints.
