Constraints can be "easy" enough to prove that a solution can be found trivially without backtracking (e.g. large sets of Wang tiles with one or more tile choices for any possible combination of edge types), "hard" enough to emulate a Turing machine (possible with Wang tiles alone), or anything in between.

Going beyond Wang tiles and corner tiles, constraints can be nonlocal, for example "the map contains 2 to 3 treasure room tiles" (which can be proved to form exactly 1 treasure room) or "river tiles belong to the same connected river component, accounting for flow direction, as a river tile on the edge of the map, or a river beginning tile, or a river end tile".

So efficient CSP solution is an engineering problem: there is the very easy case (no backtracking), the hard case (let's search for a couple of hours with a state of the art constraint solving package) and the interesting generic case (general constraints, used with significant restraint for efficiency reasons; complex but hopefully quick computation; interactive assistance to signal unsolvable and close to unsolvable sets of constraints and their problem sites.