Questions tagged [constraint-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
18
votes
1answer
2k views

When to use SAT vs Constraint Satisfaction?

If I have a hard problem, one standard approach is to express it as a SAT instance and try running a SAT solver on it. Another standard approach is to express it as a constraint satisfaction problem, ...
3
votes
1answer
389 views

Efficient algorithm to fulfil a set of coordinate constraints

I have a set of labelled points and a set of distance constraints between pairs of points, consisting of a lower and upper distance bound. There is definitely an arrangement of the points in 3D space ...
6
votes
2answers
603 views

How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints?

Best reference I could find is this one. However, I could not quite understand this one since there is no numerical example. What I am trying to achieve with one sentence How can I answer the ...
4
votes
1answer
241 views

transformation of constraint satisfaction to SAT

How can any Constraint satisfaction problem be converted to an instance of Satisfiability? I have a CSP and i know its NP hard to solve it, but i would like to convert to an instance of k-SAT, but im ...
1
vote
1answer
139 views

Requiring at least one alldiff constraint to be satisfied converted to SAT

For generating certain hard puzzles, I am trying to model a problem (ultimately) in SAT. I don't know how to do that, so I am starting with CSP because it's more expressive. In CSP, there is a global ...