Earlier quoted context omitted.
When you say "all open pieces have at least 2 possible values", how can the solution be unique ? Surely for each piece, some values are not admissible, otherwise this would be a contradiction. Sufficiently strong pruning could have eliminated them, either by search or by more reasoning.
Consider the Eight Queens problem. There are multiple valid solutions to the problem on a given chessboard. They are symmetric solutions, yet distinct. Any algorithm that finds a single solution and not all of them must be prioritizing arbitrarily among solutions, i.e., searching or fathoming them in some particular order. > This solution is found via constraint propagation alone. This means that the system has deduc…
"involves some attempt to further reduce the feasible set associated with the node by applying logical rules"
These propagation rules are among the major attractions of CP, and distinguish the paradigm from uninformed search strategies that have to consider much larger portions of the search space in general. I think a description of CP should put at least equal emphasis on this pruning mechanism as on the actual search itself, because sufficiently strong propagation may render the search completely unnecessary. In fact, this is exactly what happens in the Sudoku example of the article!
In a sibling thread, sfrank has cited a very important reference as an example of such a propagation algorithm, which serves to illustrate this idea and is also widely used in practice in CP systems and their applications:
A filtering algorithm for constraints of difference in CSPs, J-C. Régin, 1994
To see this algorithm in action, consider the following example: Take three variables X, Y and Z, all of them integers that are either 0 or 1, with the additional constraint that they must be pairwise distinct. In Prolog with CLP, and said algorithm available under the name all_distinct/1, we can state this task as follows:
?- X in 0..1, Y in 0..1, Z in 0..1,
all_distinct([X,Y,Z]).
false.
?- X in 0..1, Y in 0..1, Z in 0..1,
X #\= Y, Y #\= Z, X #\= Z.
X in 0..1,
X#\=Z,
X#\=Y,
Z in 0..1,
Y#\=Z,
Y in 0..1.
?- X in 0..1, Y in 0..1, Z in 0..1,
X #\= Y, Y #\= Z, X #\= Z,
label([X,Y,Z]).
false.
?- X in 0..1, Y in 0..1, Z in 0..2,
all_distinct([X,Y,Z]).
Z = 2,
X in 0..1,
all_distinct([X, Y, 2]),
Y in 0..1.
This shows that you can arrive at a solution (or prove the lack of a solution) either via a search or by using a sufficiently strong propagation mechanism. Doing more of one requires less work of the other. Please note that, as I said before, you indeed need an explicit search in general, because the propagation algorithms alone are, while often quite effective, not effective enough in general to guarantee consistency when different constraints interact, even if they guarantee domain consistency individually. This is a practical trade-off between propagation strength and efficiency of the available constraints. You also need search to enumerate all solutions, if there are more than one. However, note that propagators are also triggered during the search, and so unifying even a single remaining variable with a concrete integer may again lead to a situation where no additional search is necessary. Thus, the initial size of the search space is not a satisfactory measure for the eventual complexity of the search, because it does not account for the additional propagation that is applied during the search itself.
Even in the case of Sudoku, and even if you use the most powerful individual all_distinct/1 constraints, you need to search, in general, to truly generate the unique solution explicitly. But the Prolog code shown in the article doesn't (hence, it will lead to floundering constraints in general), and the concrete puzzle shown in the article is, coincidentally or not, correctly solved just by such propagation algorithms, without any search. This situation is also not particularly rare: In many cases of practical importance, constraint propagation alone already tightens remaining domains so significantly that no or only very little additional search is necessary.
Thus, everything you said is true: Yes, you need search in general, also when using CP, to obtain concrete solutions. However, to repeat, it is quite different from what one would call "brute force" search because the sophisticated and often very effective propagation algorithms prune the search space, often substantially, and can moreover help to guide the search with various heuristics. In practice, you typically buy a Prolog system just to benefit from these propagation algorithms! Various notions of consistency exist, and you can find more such algorithms in the literature references that are for example included in SICStus Prolog and other Prolog systems with constraints.
Second, note that the description you quote does not even cover the particular case that arises in the article and also many other cases in practice: That is, there are no nodes at all, because everything is already settled by constraint propagation before any search even starts, making the whole solution explicitly available without search.
The Eight Queens problem you cite is quite different from Sudoku, because it may have multiple solutions. For this reason, as you correctly observe, search is needed to generate the different solutions in such cases. But this does not invalidate the Sudoku example, where we know that exactly one solution exists, and sufficiently strong pruning could always determine it, whether by internal propagation or other algorithms that simply eliminate all values that do not participate in the unique solution of the puzzle. Nor does it show that the cost for the search outweights that of constraint propagation in either case.
For these reasons, I recommend to put at least equal focus on constraint propagation as on the search when discussing CP.