Multiplication vs Exponent Constraints

In the Dudeney problem we have the constraint:

solver.Add(nb = s*s*s)

and the model that I have shown previously finishes with 92 fails with a labeling on x.

But behind the scene, google solver is smart because it doesn’t post multiplication constraints only. The first multiplication introduces a variable (call it t) with the constraint (t==s^2) (an exponent two constraint). Then the multiplication constraint (nb==t*s) is posted.

Is it important? Yes for the pruning of the domains. And CP is all about pruning!

Let’s consider some domains on our variables to realize this. Assume that s has a domain [1..10] and t has a domain of [25..100]. Then you can prune the interval of s to [5..10] with the power two constraint. With a simple multiplication you can only prune it to [3..10].

If you want to see the effect on the Dudeney problem with only multiplication we can post this such that the solver has no way to know that a power two constraint can be posted:

s1 = solver.IntVar(range(1,9*n+1),'s1')
solver.Add(s1 == s)
solver.Add(nb == s*s1*s)

And now you get 5821 fails!

Can we do better in this case?

Yes if you have a power three constraint ;-) But this is generally not implemented in solvers because it’s not so used.

You can also do better on the Dudeney problem with a labeling on another decision variable but this is another story...