Constraint Programming is "on the same complexity" as any of your NP-completeness set of problems.

IE: Knapsack problem, Traveling Salesman, etc. etc.

Today, it seems more popular to use "3-SAT Solvers". But constraint programming is "more logical" for some problems to get converted into rather than 3-SAT. Consider 3-SAT and Constraint Programming to be two different "assembly languages" that you can compile your problem into, and then have a generic solver into.

-----------

For example: Sudoku can be "compiled" into the 3SAT problem: https://www.mit.edu/~6.005/sp12/psets/ps2/ps2.html

But it also can be "compiled" into the Constraint-problem, which then gets solved by a constraint solver. https://sonalake.com/latest/constraint-programming-solving-s...

------------

Personally speaking, I think that the constraint solver problem is "easier to compile into" rather than the 3SAT problem, especially when you consider generic constraints that have very efficient solutions.

For example, it is difficult to think of the optimal alldifferent constraint within 3SAT, but in a constraint-solver framework, its just... well... alldifferent. So you can describe Sudoku as the following:

    Domain = {1 2 3 4 5 6 7 8 9}
    Alldifferent(X11, X12, X13, X14, X15, X16, X17, X18, X19)
    Alldifferent(X21, X22, X23, X24, X25, X26, X27, X28, X29)
    Alldifferent(X31, X32, X33, X34, X35, X36, X37, X38, X39)
    ...    
    Alldifferent(X91, X92, X93, X94, X95, X96, X97, X98, X99)
    ------------------------------------------------------------------------
    Alldifferent(X11, X21, X31, X41, X51, X61, X71, X81, X91)
    Alldifferent(X12, X22, X32, X42, X52, X62, X72, X82, X92)
    Alldifferent(X13, X23, X33, X43, X53, X63, X73, X83, X93)
    ...
    Alldifferent(X19, X29, X39, X49, X59, X69, X79, X89, X99)
    ------------------------------------------------------------------------
    Alldifferent(X11, X12, X13, X21, X22, X23, X31, X32, X33)
    ...
    Alldifferent(X77, X78, X79, X87, X88, X89, X97, X98, X99)

That is: numbers are 1 through 9, and constrain the problem such that each row is alldifferent, and each column is all different, and each "3x3 square" is all different.

----------

IIRC, the Alldifferent constraint can be efficiently solved using maximum flow. So you write a specialized solver for alldifferent using maximum flow (faster than 3SAT / NP Completeness), and this maximum-flow local solution can be "plugged into" the rest of the constraint solver problem, and integrates cleanly with the rest of the solver's NP-completeness search.