[gkatsi]

I think it is a mistake to try to characterize when CP works based on constrainedness or on the number of solutions. In fact, being loosely constrained is typically used to imply that a problem is easy. The problem for CP is when a problem is NOT loosely constrained, but propagation is weak. This means that whatever reasoning we can do with the set of constraints, we cannot express as value prunings.

As for the number of solutions vs constrainedness: as far as I know, the only domain in which there exists a clear theoretical understanding of number of solutions vs difficulty is random problems, where we see an "easy-hard-less hard" pattern as we increase the density for a fixed size problem. What happens there is that there is an exponential number of solutions in the easy region which form a small (polynomial number) of very big clusters. As we get to the hard region, the number of solutions remains exponential, but the solution space shatters into an exponentially large number of clusters. The definition of a cluster in this case is: if two solutions have constant Hamming distance, they are in the same cluster. On the other hand, some unsatisfiable problems (so 0 solutions) are very very hard for CP and related approaches.

All this is just to say that the picture is much more complicated than you say and the best way to figure out if CP is a good fit for an application is to try it. People develop intuition over time of course, but the issue is far from understood.