Regarding the strength of different solvers: The solution I posted is just one out of many possible constraint-based formulations of Sudoku, using one particular domain and one particular solver implementation. In this concrete case, I have used constraint logic programming over integers, also known as CLP(FD), which is available in many Prolog systems. This is one of the most important and most prominent applications of constraint logic programming and even of logic programming in general.

As an alternative, we can just as well model Sudoku puzzles as combinatorial tasks over Boolean variables, and hence use CLP(B), constraint logic programming over Booleans.

For example:

    sudoku(Rows) :-
            length(Rows, 9), maplist(same_length(Rows), Rows),
            maplist(row_booleans, Rows, BRows),
            maplist(booleans_distinct, BRows),
            transpose(BRows, BColumns),
            maplist(booleans_distinct, BColumns),
            BRows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
            blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is).

    blocks([], [], []).
    blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
            booleans_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
            blocks(Ns1, Ns2, Ns3).

    booleans_distinct(Bs) :-
            transpose(Bs, Ts),
            maplist(card1, Ts).

    card1(Bs) :- sat(card([1],Bs)).

    row_booleans(Row, Bs) :-
            same_length(Row, Bs),
            maplist(cell_boolean, Row, Bs).

    cell_boolean(Num, Bs) :-
            length(Bs, 9),
            sat(card([1],Bs)),
            element(Num, Bs, 1).

In this formulation, I use 9 Boolean variables to represent which of the 9 possible integers is assigned to a particular cell.

Let us apply this formulation to puzzle (b) that is shown in the solution of this exercise:

    knuth(b, [[1,_,3,_,5,6,_,8,9],
              [5,9,7,3,8,_,6,1,_],
              [6,8,_,1,_,9,3,_,5],
              [9,5,6,_,3,1,8,_,7],
              [_,3,1,5,_,8,9,6,_],
              [2,_,8,9,6,_,1,5,3],
              [8,_,9,6,_,5,_,3,1],
              [_,6,5,_,1,3,2,9,8],
              [3,1,_,8,9,_,5,_,6]]).

Here is the result:

    ?- knuth(b, Rows),
       sudoku(Rows),
       maplist(portray_clause, Rows).
    [1, 2, 3, 4, 5, 6, 7, 8, 9].
    [5, 9, 7, 3, 8, 2, 6, 1, 4].
    [6, 8, 4, 1, 7, 9, 3, 2, 5].
    [9, 5, 6, 2, 3, 1, 8, 4, 7].
    [7, 3, 1, 5, 4, 8, 9, 6, 2].
    [2, 4, 8, 9, 6, 7, 1, 5, 3].
    [8, 7, 9, 6, 2, 5, 4, 3, 1].
    [4, 6, 5, 7, 1, 3, 2, 9, 8].
    [3, 1, 2, 8, 9, 4, 5, 7, 6].

For comparison, here is the result of the CLP(FD)-based formulation that I posted earlier:

    ?- knuth(b, Rows),
       sudoku(Rows),
       maplist(portray_clause, Rows).
    [1, _, 3, _, 5, 6, _, 8, 9].
    [5, 9, 7, 3, 8, _, 6, 1, _].
    [6, 8, _, 1, _, 9, 3, _, 5].
    [9, 5, 6, _, 3, 1, 8, _, 7].
    [_, 3, 1, 5, _, 8, 9, 6, _].
    [2, _, 8, 9, 6, _, 1, 5, 3].
    [8, _, 9, 6, _, 5, _, 3, 1].
    [_, 6, 5, _, 1, 3, 2, 9, 8].
    [3, 1, _, 8, 9, _, 5, _, 6].

This shows that CLP(B), in contrast to CLP(FD), has determined the unique solution without any search. This is an example of a solver that propagates as strongly as possible, and hence achieves global consistency even across different constraints.

It also works for puzzle (a):

    ?- knuth(a, Rows),
       sudoku(Rows),
       maplist(portray_clause, Rows).
    [1, 2, 3, 4, 5, 6, 7, 8, 9].
    [5, 9, 8, 7, 2, 1, 4, 3, 6].
    [7, 6, 4, 3, 8, 9, 2, 5, 1].
    [8, 4, 2, 1, 9, 3, 6, 7, 5].
    [9, 7, 5, 2, 6, 4, 8, 1, 3].
    [6, 3, 1, 8, 7, 5, 9, 4, 2].
    [3, 1, 6, 9, 4, 8, 5, 2, 7].
    [4, 5, 7, 6, 3, 2, 1, 9, 8].
    [2, 8, 9, 5, 1, 7, 3, 6, 4].

At this point, you may wonder: Why have I started with (b) instead of (a)? The reason is easy to explain: For puzzle (a), the strong propagation of the CLP(B)-based formulation took so long that it only completed now, after I have finished typing this, a few minutes after I had posted the query, whereas it only took a few seconds for example (b).

Both examples have taken considerably longer to solve with CLP(B) instead of CLP(FD). That's not to say that one approach is better than the other in general or even in that particular case - instead, it is more an observation about the solver implementations and the chosen trade-offs between propagation strength and efficiency in both solvers.

CLP(B) achieves this strong consistency by internally considering, in a sense, the totality of all possible assignments, and this may require exponential space and hence also time. But for many important practical cases, the representation used by CLP(B) is very efficient, and indeed allows us to solve tough problems efficiently. Note that still, no search is involved here: Even the internal propagation of CLP(B) proceeds completely deterministically, and at no point in the computation do we have to guess anything.

It must also be said that the CLP(FD)-based formulation, in addition to being faster (despite the necessary search), is also shorter and arguably more natural than the Boolean variant. Casting this as an exact cover or hitting set task can definitely be done, either with CLP(B) or CLP(FD) constraints (since Booleans can also be considered as a special case of integers). However, it takes us even further away from the quite direct and readable "natural" CLP(FD) formulation. For cover problems in general, I recommend you obtain a CLP(B) solver that internally uses Zero Suppressed Binary Decision Diagrams (ZDDs). They let you efficiently represent cases where many of the variables (such as row selection indicators) are zero, which is typical for covering tasks.