# Questions tagged [constraint-satisfaction]

The tag has no usage guidance.

144 questions
Filter by
Sorted by
Tagged with
21 views

### Is minimum interval hitting problem NP-HARD?

Consider this problem: We want to mark some integer numbers such that we mark the minimum number of the numbers and satisfy some constraints. Each constraint wants that at least $k$ numbers in ...
26 views

### Bipartite matching with constraints on one part

We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b_1$ and $b_2$ both from part $B$,...
60 views

### Minimal set of elements needed to satisfy property counts

I have a friend who works in education. Sometimes, they need to create customized "word lists" to help students practice reading. These lists are limited in length, and must contain ...
24 views

### Solving the constraint portion of the input-encoding problem

The "input-encoding problem" is where the binary representations of symbolic input variables to a Boolean function are chosen to minimize the decode logic complexity. The "Espresso-MV&...
1 vote
40 views

### Efficient way to calculate many Dutch auctions?

I have 4,500 ($N$) unique items, and I want to auction each one off to the highest bidder (break ties arbitrarily). Each item has $T$ binary traits. Since it is too complex for the $B$ bidders to ...
9 views

1 vote
341 views

### How does the SMT solver Z3 handle conditional statements in a constraint?

I have a constraint system which I seek to find solutions for. The constraints consist of lesser/equal inequalities which have a difference of two minimum expressions on their right side, for example: ...
1 vote
202 views

### How to design a faster sort algorithm? Is there sort of meta-algoritm for it? Or we do not understand how better sort algorithms were discovered?

I know that Quicksort or MergeSort are faster than, say, Bubblesort or Selection sort. And I know why (complexity metrics) but I never been able to find out how could someone start with, for example ...
33 views

40 views

### Can arc consistency checks be avoided if constraints are formulated properly?

While solving a few CSPs by hand, I noticed that I don't actually need to check for arc consistency after each assignment. All I needed to do was to formulate the CSP in such a way that I'm adding ...
48 views

### CSP heuristics to help avoid redundancy while checking values for constraint inconsistency?

I'm a complete beginner. Please forgive my ignorance.Trying to learn about CSP online, I noticed a lot of the focus on search methods and heuristics which tell you which variable to expand next (e.g. ...
270 views

### How can we formulate an anti-knight Sudoku as an exact cover problem?

Formulating standard Sudoku as an exact cover problem is easy and well documented. All of the constrained groups contain every digit which makes it natural to express the problem this way. Wikipedia ...
1 vote
236 views

### Counting the number of satisfied models - given mathematical constraints

Question There are plenty of algorithms for solving the #SAT problem, with one being the DPLL algorithm and is implemented for all kinds of programming languages. As far as I've seen, they all take a ...