# Can I do constraint programming in Mathematica? [closed]

I would like to know if there is a way to do constraint programming in Mathematica? I think there are no built-in functions, but maybe some of you know some additional packages addressed to the constraint satisfaction problem.

Update

@Histograms mentioned FindInstance but I have to say that I have tried it before but it works a bit strange consider example below:

system = {
-(1/2) + x + (1 - θ^2)/( 1 + θ^2) + (1 - (1 - θ^2)/( 1 + θ^2)) ω1^2 > 0,
1/2 + x + (1 - θ^2)/( 1 + θ^2) + (1 - (1 - θ^2)/(1 + θ^2)) ω1^2 > 0,
-(1/2) + y + (1 - (1 - θ^2)/(1 + θ^2)) ω1 ω2 + (2 θ ω3)/(1 + θ^2) < 0,
1/2 + y + (1 - (1 - θ^2)/(1 + θ^2)) ω1 ω2 + (2 θ ω3)/(1 + θ^2) > 0,
-(1/2) + z - (2 θ ω2)/( 1 + θ^2) + (1 - (1 - θ^2)/(1 + θ^2)) ω1 ω3 < 0,
1/2 + z - (2 θ ω2)/(1 + θ^2) + (1 - (1 - θ^2)/(1 + θ^2)) ω1 ω3 > 0,
-∞ <= θ <= ∞,
{ω1, ω2, ω3} ∈ Sphere[{0, 0, 0}, 1],
0 <= ω1 <= ω2 <= ω3 <= 1,
-(1/2) < x < 1/2,
-(1/2) < y < 1/2,
-(1/2) < z < 1/2};

FindInstance[system, {θ, ω1, ω2, ω3, x, y, z}, Reals, 1]
(*change n to two to get the answer*)


In Mathematica 10.0.2 I cannot get any answer for n = 1, it just run all the time. But if I change it eg to 2 I get answer almost immediately. Any suggestions what is wrong?

• In principle you can do Prolog in any language – Dr. belisarius Jun 13 '15 at 7:20
• Well FindInstance is basically a SAT solver, and Select and Cases are pretty useful. – Histograms Jun 13 '15 at 7:49
• @Histograms well I've tried FindInstance before and I have a problem with it. In particular, for my problem it gives me very quickly more than one solutions but if I will call it with n == 1 it cannot finish... – marekszpak Jun 13 '15 at 11:14
• @marekszpak well if you want help with that particular problem you know where to come. You should also try Select if you're able to pre-generate lists of potential solutions to seive. – Histograms Jun 13 '15 at 14:37
• @image_doctor Here mathematica-journal.com/issue/v4i1/columns/maeder/… – Dr. belisarius Jun 13 '15 at 15:41

I was able to generate one instance (the all-zeros solution) but FindInstance refuses to generate 2 or more for me (v10.1) using the final argument, despite copious solutions existing.

Horrible hack incoming in 3... 2... 1:

(* N.B I removed your greek and the sphere constraint is now Ball.
If you only want the surface of the sphere, then Sphere is fine,
but only works up to ninstances = 2 giving:
{{x -> 0, y -> 0, z -> 0, t -> 0, w1 -> 0, w2 -> 0, w3 -> 1},
{x -> 15/32, y -> 1/4, z -> -(1/4), t -> -1, w1 -> 1/4,
w2 -> 1/2, w3 -> Sqrt[11]/4}} *)

system = {
-1/2 < x < 1/2,
-1/2 < y < 1/2,
-1/2 < z < 1/2,
-(1/2) + x + (1 - t^2)/(1 + t^2) + (1 - (1 - t^2)/(1 + t^2)) w1^2 > 0,
1/2 + x + (1 - t^2)/(1 + t^2) + (1 - (1 - t^2)/(1 + t^2)) w1^2 > 0,
-(1/2) + y + (1 - (1 - t^2)/(1 + t^2)) w1 w2 + (2 t w3)/(1 + t^2) < 0,
1/2 + y + (1 - (1 - t^2)/(1 + t^2)) w1 w2 + (2 t w3)/(1 + t^2) > 0,
-(1/2) + z - (2 t w2)/(1 + t^2) + (1 - (1 - t^2)/(1 + t^2)) w1 w3 < 0,
1/2 + z - (2 t w2)/(1 + t^2) + (1 - (1 - t^2)/(1 + t^2)) w1 w3 > 0,
{w1, w2, w3} \[Element] Ball[{0, 0, 0}],
0 <= w1 <= w2 <= w3 <= 1};

newsystem = system; i = 0; ninstances = 10;
Flatten[Reap@
While[i < ninstances,
newsystem =
Flatten[Append[newsystem,
First[Sow[
FindInstance[And @@ newsystem, {x, y, z, t, w1, w2, w3},
Reals, 1]]] //. Rule -> Unequal]];
i++], 3] // Rest


I noticed that if you get a single instance from FindInstance then you append an extra constraint to the system that the solution cannot be the previous one, rinse and repeat, you can generate more solutions. Of course, this is an absolutely horrific way of getting around FindInstance failing to do as it's told and just give us multiple solutions out of the box without hanging.

• thanks! Well, my system from example above is just a demo. In real case I have to work with something a bit bigger around 40 strict inequalities. Well, I added just 6 more inequalities to my system and FindInstance again cannot finish. I was worried from the very beginning that my shell constraint makes a lot of troubles here. Do you have any idea how I could speed up FindInstance for more general cases? – marekszpak Jun 14 '15 at 15:49
• @marekszpak no I'm afraid FindInstance is hopeless. I've been playing around with it and crikey, what a nightmare. At this point I'm thinking generate the w1,w2,w3 in the shell randomly, then use Reduce after substituting them into the system. – Histograms Jun 14 '15 at 15:57