Questions tagged [constraint-satisfaction]
The constraint-satisfaction tag has no summary.
155 questions
2 votes
1 answer
126 views
How to find a bijection $\Phi$ that maximizes the number of iterative replacements in a local rewriting system on $\left\{ 0, 1, 2, 3 \right\}$?
Problem. We study a local rewriting map defined on $5$-letter words over the alphabet $\{0,1,2,3\}$. A fixed forbidden-block set $\mathcal{F}$ of $16$ length-$3$ patterns is given by $$\mathcal{F}= \{...
- 111
1 vote
1 answer
58 views
AC-3 algorithm and requeueing
I'm watching CS50AI's week 3 video, particularly the part describing the AC-3 algorithm, which starts at around 1h 10m. I'll paraphrase the algorithm ...
- 111
1 vote
0 answers
53 views
Is it possible to modify the transportation problem to enforce that each destination is supplied by only one source?
Problem Description: I have a standard transportation problem with: m sources, each with a given supply capacity. n destinations, each with a specific demand. A cost associated with transporting ...
- 11
1 vote
0 answers
58 views
Can we construct the circular permutation from partial partitions?
Imagine a circular permutation of n points on a circle, if we draw a line connecting any pair of points, the rest of the points are divided into two sets that are on the same side. We can partition a ...
- 11
1 vote
1 answer
112 views
Applications of a SAT Solver Oracle for Determining the Uniqueness of Solutions
I am exploring two kinds of model $π_{π,π,k}$ and $S_{m,n,k}$ within the realm of satisfiability problems (SAT). Formal construction of $π_{π,π,k}$ To construct the $π_{π,π,k}$ model in ...
- 399
1 vote
0 answers
53 views
Resolving distance constraints in 2D
I am currently writing a tool that will be used in an industrial process to place components with physical requirements. It boils down to the following: I have a set of points (typically, a few ...
- 111
0 votes
1 answer
404 views
How fast can we make generalized k-SAT?
Suppose a generalized version of k-SAT where the usual clauses (disjunctions of literals) are generalized to arbitrary Boolean functions of k variables. (For example, $(x \oplus (y \land z)), ((x \...
user150715
1 vote
0 answers
76 views
Understanding Arc Consistency 4 in the context of Wave Function Collapse
Following this blog post about the Arc Consistency algorithms. Namely, the explanation on AC4. Consider the following example: If I understand AC problems correctly. Then: We have two known ...
- 111