# Questions tagged [constraint-satisfaction]

The tag has no usage guidance.

85 questions
Filter by
Sorted by
Tagged with
426 views

### How could an SMT solver be implemented as simple as possible?

I'm trying to figure out how an SMT solver works as simple as possible. Let's assume we have a simple input program with symbolic values x and ...
40 views

### Constraint-based layouts for GUIs

The VPRI institut founded by Alan Kay has some papers on constraint-based layouts for GUIs based on constraint solving. For instance: Wallingford: Toward a Constraint Reactive Programming Language ...
272 views

### Binarization of Constraints

I am trying to solve a Constraint Satisfaction Problem that involves lots of n-ary constraints. But the solver I have implemented only works with algorithms for binary constraints. I've been reading ...
978 views

### CSP Forward checking with n-ary (and binary) constraints

I have implemented my own CSP solver using a Backtracking algorithm. Within the Backtracking algorithm I apply a Forward Checking algorithm (reducing domains of connected, unnasigned variables) that ...
483 views

### Finding multi word anagrams from a set of words

Finding all anagrams for a word $w$ from a set of words is a problem with many well-known solutions (for example make a hash table mapping from the bag of letters of a word to the word). But what ...
57 views

### Small world theorem for set constraints

Let $S_1,\dots,S_n$ be variables representing unknown sets. A set expression has the form $S_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions. A ...
47 views

### Handling eqaulity constraints in genetic algorithms

I am trying to solve an optimization problem with strength pareto algorithm (SPEA2). My decision variable have lower and upper bounds as well as an equality constraint (sum(dp) = 1). I am unable to ...
180 views

### Efficient algorithm for simple constraint satisfaction problem

There are $k$ Boolean variables $x_1, x_2, \dots, x_k$. $m$ arbitrary subsets of these variables such that sum of each set equals to $1$ (i.e., only one variable is $1$, the others are $0$). E.g., ...
189 views

### Modeling tiling problems as SAT problems

I read that tiling problems can be modeled as satisfiability problems (2-SAT?), but the author did not explain how. Is this true? What would be an example? By a "tiling problem" I mean you have a ...
53 views

### “strongly relational m-consistency when the domains contain at most m elements implies satisfiability” plain wrong?

Wikipedia states A constraint satisfaction problem may be relationally consistent, have no empty domain or unsatisfiable constraint, and yet be unsatisfiable. There are however some cases in ...
413 views

### Heuristic Repair and N-Queens Problem

Problem: I am trying to solve the $N$-Queens problem using Constraint Satisfaction and Heuristic Repair (also known as Min-Conflicts). I wrote a program to do this for any given $N$ queens and $N * N$...
66 views

### (Historical perspective) CSP and SAT inter-fertilization

[Disclaimer: this is a rather specialized question] It is known that techniques like Conflict-Driven Clause Learning (CDCL) and back-jumping -- which improved the Satisfiability (SAT) strategies ...
129 views

### Any reason to use the least-constrained variable heuristic when searching the solution of a CSP?

Is there any (kind of) (well-known) problem which can be expressed as a CSP in which the least constrained variable heuristic seems to give the best results, when employing backtracking with ...
5k views

12k views

### What is Least-Constraining-Value?

In constraint satisfaction problems, heuristics can be used to improve the performance of a bactracking solver. Three commonly given heuristics for simple backtracking solvers are: Minimum-remaining-...
775 views

### Contraint with three variables into three binary constraints

I'm having a hard time tackling the following problem (perhaps some key data is missing). We have a constraint: $A+B= C$ One is supposed to represent this one constraint using three binary ...
142 views

### Isn't Domain of a variable nothing but a constraint?

In Constraint programming we have Variables and their Domains and then all the constraints, but if you at the concept of a domain of a variable it is nothing but another type of constraint, you are ...
1k views

### Why don't modern SAT solvers use the notion of a “watched clause”, in the same way they use the notion of a “watched literal”?

Modern SAT solvers use the notion of "watched literals": when a value is chosen for a literal $l$, the solver only checks whether that falsifies clauses with $l$ in them if $l$ is one of the watched ...