Stack Overflow
Stack Overflow

Questions tagged [constraint-satisfaction]

79 questions
24
votes
3 answers

What are the differences between simulated annealing and genetic algorithms?

What are the relevant differences, in terms of performance and use cases, between simulated annealing (with bean search) and genetic algorithms? I know that SA can be thought as GA where the population size is only one, but I don't know the key…
Kevin
  • 6,711
  • 16
  • 60
  • 107
12
votes
1 answer

Unparse AST < O(exp(n))?

Abstract problem description: The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST. So parse(unparse(AST)) = AST holds. This is the equal to finding a valid parse tree which would…
Stefan K.
  • 7,701
  • 6
  • 52
  • 64
11
votes
1 answer

How to perform constraint solving with mixed data types?

I'm working on source-to-source transformer for Java 6*1). I need to maintain negative information as well as positive information, so I have to implement the small constraint system for the transformer. The constraint system is the restricted kind…
Anton Danilov
  • 1,246
  • 11
  • 26
9
votes
1 answer

Optimal 4 Word Placement Inside Arbitrarily Sized Grid

Problem statement: Given four words, place them inside a m x n grid of squares such that the area of the grid is as small as possible. Words must run from left to right and from top to bottom inside the grid. Letters may overlap, but additional…
Auburnate
  • 437
  • 1
  • 4
  • 11
8
votes
9 answers

Possible NP-complete problem?

I'd just like someone to verify whether the following problem is NP-complete or if there is actually a better/easier solution to it than simple brute-force combination checking. We have a sort-of resource allocation problem in our software, and I'll…
Lasse V. Karlsen
  • 380,855
  • 102
  • 628
  • 825
8
votes
1 answer

Why is the complexity of Arc-Consistency Algorithm O(cd^3)?

Why is the complexity of Arc-Consistency Algorithm O(cd3)?
ark
  • 81
  • 1
  • 3
6
votes
4 answers

Permutations of a list with 16 integers but only if 4 conditions are fulfilled

I have a list of integers keys = [18, 99, 86, 61, 66, 81, 98, 19, 91, 16, 69, 88, 89, 68, 11, 96] I'd like to find all permatutations of this list such that for each permutation elements 0 through 3 add up to 264, elements 4 through 7 add up to…
Olba12
  • 305
  • 2
  • 14
5
votes
3 answers

Fill a 6x6 grid with 6 colors without same colors touching each other

I'm trying to create a board game with p5.js (Javascript) To set up the game board which is a 6 by 6 grid, I have to fill the grid with 6 colors in a way that no horizontal or vertical touching cells have the same color. And all 6 colors have to be…
simusch
  • 51
  • 4
5
votes
1 answer

AC-1, AC-2 and AC-3 algorithms (arc-consistency)

Anyone can explain to me the AC-1, AC-2 and AC-3 algorithms ? I have to understand them and implement them with code. But first, I want to understand them really good, But they are just too tough to be understood by me. Any help please? Btw, I'm…
user4491463
4
votes
0 answers

Solve Record Linkage as a Constraint Satisfaction with Machine Learning

I have pairs of sets such as A = { L, M, N, P } = { <"Lll", 47, 0.004>, <"Mm", 60, 0.95>, <"Nnnn", 33, 0.2892>, <"P", 47, 0.0125> } B = { l, m, n, o } = { <"l", 46, 0.004>, <"m", 0, 0.95>, <"nn", 33, 0.2892>, <"oOo", 33, 0.5773> } ... and I…
Jason Kleban
  • 20,024
  • 18
  • 75
  • 125
3
votes
1 answer

Pulp Killer sudoku - check choices are distinct for choice of variables

I am trying to solve killer Sudoku using Python linear optimization library, Pulp. https://en.wikipedia.org/wiki/Killer_sudoku Here is my attempt so far, adding a constraint that each row must add up to 45. import pulp prob = pulp.LpProblem("Sudoku…
oli5679
  • 1,709
  • 1
  • 22
  • 34
3
votes
2 answers

Building up timetabling problem with lots of variables

I have a classic timetabling problem consisting of the variables classes(~100), rooms(20),terms(8) and weekdays(5). To just simplfy the problem, following are the reduced constraints. A day is 9 hours. Some classes are mandatory for students, and…
altunyurt
  • 2,821
  • 3
  • 38
  • 53
3
votes
2 answers

Make a constraint more difficult to solve for a constraint solver?

I am a newbie to SMT solving and I am writing to inquire some advice and pointers to understand what is a really difficult constraint for SMT solver to solve, for instance Z3. I tried to tweak the length of bit vectors, for instance in the following…
lllllllllllll
  • 8,519
  • 9
  • 45
  • 80
3
votes
2 answers

Get Prolog to give all possibilities for arithmetic

I was wondering whether in prolog it is possible to get it to brute force all the possible calculations for something like this: 6 is Z + Q Z = 1 Q = 5 Z = 2 Q = 4 Z = 3 Q = 3
user3667111
  • 611
  • 6
  • 21
3
votes
1 answer

minisat how to find all the SAT solutions efficiently

I found a way to finding all the solutions using the way described in this link. This is working fine, but it is slow. As it recalculates the constraints from the start i_e doesn't take advantage of the previous computations. Now, I saw in this …
Gaurav Singh
  • 31
  • 1
1
2 3 4 5 6