Constraint Programming and Constrained Optimization are not really the same thing.  An example of constraint programming is the 8 queens problem, how to put 8 queens on a chess board so that they can't attack each other.  There's no objective function.

Mathematica doesn't really do logic programming (like prolog). It's not hard to implement something though:

The Mathematica Programmer: Logic Programming I: The Interpreter

I've done some experimenting on a graph coloring problem with 20 nodes and 23 edges, coloring the nodes with 3 different colors.
Using FindInstance with Integer variables I can solve the problem in about 3 seconds.  Using FindInstance with 3 Boolean variables on each node, I can solve the problem in about 1.5 seconds.  Converting the problem to a mixed integer linear programming formulation with 3 binary variables on each node, I can solve the problem in 11 mSec using NMinimize.  For the FindInstance approach with 3 Boolean variables on each node, I used the BooleanCountingFunction to generate the constraints that only one variable on each node is True and that at most one variable is True for the corresponding variables on nodes connected by edges.