Constraint Satisfaction Problem formulation
up vote
2
down vote
favorite
I am given the following requirements which need to be formulated into a CSP problem by defining a set of variables, and a set of constraints over those variables. However I'm having trouble formulating the constraints and variables for my problem.
Some info:
The solution to the problem is a list of assignments: [Var, A1, A2, A3]
where Var
is the variable and A1
, A2
, A3
is an ordered sequence of valid assignments.
Requirements:
- Each variable is assigned a value in
problem.valid_assignments()
- Each variable's first assignment is in
problem.first_assignments()
- Each variable's assignment sequence is in
problem.valid_pairs()
(Some assignments can't follow others) - Given an integer
K
, there can be no more thanK
continuous assignments where at least one is not in problem.k_assignment() - Every value in the given assignments list:
problem.assignment
must be used.
Available Constraints:
NValues
constraint: Given a list ofrequired_values
, an upper bound and lower bound, makes sure that the number of variables whose value is inrequired_values
is between the bounds.
AllDifferent
constraint: Given a set of variables, enforces their inequality. That is no two variables in the set are equal.
NotEqual
constraints: GivenVar1
,Var2
, enforces:Var1
!=Var2
So Far:
- A Variable for each
Var
whose domain isproblem.valid_assignments()
- A Variable for each
Var
whose domain isproblem.first_assignments()
- A
NValues
constraint for eachVar
whose scope is[Var]
, required valuesproblem.valid_assignments(Var)
, lower bound0
, upper boundlen(domain)
.
Additional info:
The solution is a "list of assignments" as in for each
Var
we return[Var, A1, A2, A3]
whereVar
is the variable assigned andA1
throughA3
are valid assignments that fulfil the given constraints. The exact format doesn't matter as I'm only looking for a conceptual solution. AdditionallyA1, A2, A3
(aka all assignments for aVar
) must obviously be in the domain of that variable. (Domains can overlap between variables).valid_pairs()
returns a list of tuples[(A1, A2), (A2,A3)]
. The constraint is such that the returned solution list (as detailed above) must have consecutive assignments that form valid pairs that are given by this function. For example if the solution is[Var, A1, A2, A4, A3]
and the valid pairs are[(A1, A2), (A2,A3)]
then the solution is incorrect as(A2, A4) (A4, A3)
is not in the list ((A1, A2)
however is a valid pair).Essentially we're looking for arc-consistency.
python search constraints backtracking constraint-programming
|
show 4 more comments
up vote
2
down vote
favorite
I am given the following requirements which need to be formulated into a CSP problem by defining a set of variables, and a set of constraints over those variables. However I'm having trouble formulating the constraints and variables for my problem.
Some info:
The solution to the problem is a list of assignments: [Var, A1, A2, A3]
where Var
is the variable and A1
, A2
, A3
is an ordered sequence of valid assignments.
Requirements:
- Each variable is assigned a value in
problem.valid_assignments()
- Each variable's first assignment is in
problem.first_assignments()
- Each variable's assignment sequence is in
problem.valid_pairs()
(Some assignments can't follow others) - Given an integer
K
, there can be no more thanK
continuous assignments where at least one is not in problem.k_assignment() - Every value in the given assignments list:
problem.assignment
must be used.
Available Constraints:
NValues
constraint: Given a list ofrequired_values
, an upper bound and lower bound, makes sure that the number of variables whose value is inrequired_values
is between the bounds.
AllDifferent
constraint: Given a set of variables, enforces their inequality. That is no two variables in the set are equal.
NotEqual
constraints: GivenVar1
,Var2
, enforces:Var1
!=Var2
So Far:
- A Variable for each
Var
whose domain isproblem.valid_assignments()
- A Variable for each
Var
whose domain isproblem.first_assignments()
- A
NValues
constraint for eachVar
whose scope is[Var]
, required valuesproblem.valid_assignments(Var)
, lower bound0
, upper boundlen(domain)
.
Additional info:
The solution is a "list of assignments" as in for each
Var
we return[Var, A1, A2, A3]
whereVar
is the variable assigned andA1
throughA3
are valid assignments that fulfil the given constraints. The exact format doesn't matter as I'm only looking for a conceptual solution. AdditionallyA1, A2, A3
(aka all assignments for aVar
) must obviously be in the domain of that variable. (Domains can overlap between variables).valid_pairs()
returns a list of tuples[(A1, A2), (A2,A3)]
. The constraint is such that the returned solution list (as detailed above) must have consecutive assignments that form valid pairs that are given by this function. For example if the solution is[Var, A1, A2, A4, A3]
and the valid pairs are[(A1, A2), (A2,A3)]
then the solution is incorrect as(A2, A4) (A4, A3)
is not in the list ((A1, A2)
however is a valid pair).Essentially we're looking for arc-consistency.
python search constraints backtracking constraint-programming
Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
– Michael Veksler
Nov 11 at 12:46
Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
– Michael Veksler
Nov 11 at 12:49
Please seed my latest edit for clarifications. @MichaelVeksler
– Ge0rges
Nov 11 at 20:57
If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
– Michael Veksler
Nov 11 at 21:05
No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
– Ge0rges
Nov 11 at 21:12
|
show 4 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I am given the following requirements which need to be formulated into a CSP problem by defining a set of variables, and a set of constraints over those variables. However I'm having trouble formulating the constraints and variables for my problem.
Some info:
The solution to the problem is a list of assignments: [Var, A1, A2, A3]
where Var
is the variable and A1
, A2
, A3
is an ordered sequence of valid assignments.
Requirements:
- Each variable is assigned a value in
problem.valid_assignments()
- Each variable's first assignment is in
problem.first_assignments()
- Each variable's assignment sequence is in
problem.valid_pairs()
(Some assignments can't follow others) - Given an integer
K
, there can be no more thanK
continuous assignments where at least one is not in problem.k_assignment() - Every value in the given assignments list:
problem.assignment
must be used.
Available Constraints:
NValues
constraint: Given a list ofrequired_values
, an upper bound and lower bound, makes sure that the number of variables whose value is inrequired_values
is between the bounds.
AllDifferent
constraint: Given a set of variables, enforces their inequality. That is no two variables in the set are equal.
NotEqual
constraints: GivenVar1
,Var2
, enforces:Var1
!=Var2
So Far:
- A Variable for each
Var
whose domain isproblem.valid_assignments()
- A Variable for each
Var
whose domain isproblem.first_assignments()
- A
NValues
constraint for eachVar
whose scope is[Var]
, required valuesproblem.valid_assignments(Var)
, lower bound0
, upper boundlen(domain)
.
Additional info:
The solution is a "list of assignments" as in for each
Var
we return[Var, A1, A2, A3]
whereVar
is the variable assigned andA1
throughA3
are valid assignments that fulfil the given constraints. The exact format doesn't matter as I'm only looking for a conceptual solution. AdditionallyA1, A2, A3
(aka all assignments for aVar
) must obviously be in the domain of that variable. (Domains can overlap between variables).valid_pairs()
returns a list of tuples[(A1, A2), (A2,A3)]
. The constraint is such that the returned solution list (as detailed above) must have consecutive assignments that form valid pairs that are given by this function. For example if the solution is[Var, A1, A2, A4, A3]
and the valid pairs are[(A1, A2), (A2,A3)]
then the solution is incorrect as(A2, A4) (A4, A3)
is not in the list ((A1, A2)
however is a valid pair).Essentially we're looking for arc-consistency.
python search constraints backtracking constraint-programming
I am given the following requirements which need to be formulated into a CSP problem by defining a set of variables, and a set of constraints over those variables. However I'm having trouble formulating the constraints and variables for my problem.
Some info:
The solution to the problem is a list of assignments: [Var, A1, A2, A3]
where Var
is the variable and A1
, A2
, A3
is an ordered sequence of valid assignments.
Requirements:
- Each variable is assigned a value in
problem.valid_assignments()
- Each variable's first assignment is in
problem.first_assignments()
- Each variable's assignment sequence is in
problem.valid_pairs()
(Some assignments can't follow others) - Given an integer
K
, there can be no more thanK
continuous assignments where at least one is not in problem.k_assignment() - Every value in the given assignments list:
problem.assignment
must be used.
Available Constraints:
NValues
constraint: Given a list ofrequired_values
, an upper bound and lower bound, makes sure that the number of variables whose value is inrequired_values
is between the bounds.
AllDifferent
constraint: Given a set of variables, enforces their inequality. That is no two variables in the set are equal.
NotEqual
constraints: GivenVar1
,Var2
, enforces:Var1
!=Var2
So Far:
- A Variable for each
Var
whose domain isproblem.valid_assignments()
- A Variable for each
Var
whose domain isproblem.first_assignments()
- A
NValues
constraint for eachVar
whose scope is[Var]
, required valuesproblem.valid_assignments(Var)
, lower bound0
, upper boundlen(domain)
.
Additional info:
The solution is a "list of assignments" as in for each
Var
we return[Var, A1, A2, A3]
whereVar
is the variable assigned andA1
throughA3
are valid assignments that fulfil the given constraints. The exact format doesn't matter as I'm only looking for a conceptual solution. AdditionallyA1, A2, A3
(aka all assignments for aVar
) must obviously be in the domain of that variable. (Domains can overlap between variables).valid_pairs()
returns a list of tuples[(A1, A2), (A2,A3)]
. The constraint is such that the returned solution list (as detailed above) must have consecutive assignments that form valid pairs that are given by this function. For example if the solution is[Var, A1, A2, A4, A3]
and the valid pairs are[(A1, A2), (A2,A3)]
then the solution is incorrect as(A2, A4) (A4, A3)
is not in the list ((A1, A2)
however is a valid pair).Essentially we're looking for arc-consistency.
python search constraints backtracking constraint-programming
python search constraints backtracking constraint-programming
edited Nov 12 at 21:42
asked Nov 10 at 22:43
Ge0rges
1,0551025
1,0551025
Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
– Michael Veksler
Nov 11 at 12:46
Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
– Michael Veksler
Nov 11 at 12:49
Please seed my latest edit for clarifications. @MichaelVeksler
– Ge0rges
Nov 11 at 20:57
If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
– Michael Veksler
Nov 11 at 21:05
No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
– Ge0rges
Nov 11 at 21:12
|
show 4 more comments
Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
– Michael Veksler
Nov 11 at 12:46
Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
– Michael Veksler
Nov 11 at 12:49
Please seed my latest edit for clarifications. @MichaelVeksler
– Ge0rges
Nov 11 at 20:57
If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
– Michael Veksler
Nov 11 at 21:05
No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
– Ge0rges
Nov 11 at 21:12
Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
– Michael Veksler
Nov 11 at 12:46
Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
– Michael Veksler
Nov 11 at 12:46
Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
– Michael Veksler
Nov 11 at 12:49
Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
– Michael Veksler
Nov 11 at 12:49
Please seed my latest edit for clarifications. @MichaelVeksler
– Ge0rges
Nov 11 at 20:57
Please seed my latest edit for clarifications. @MichaelVeksler
– Ge0rges
Nov 11 at 20:57
If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
– Michael Veksler
Nov 11 at 21:05
If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
– Michael Veksler
Nov 11 at 21:05
No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
– Ge0rges
Nov 11 at 21:12
No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
– Ge0rges
Nov 11 at 21:12
|
show 4 more comments
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
We can use an
NValues
constraint whose scope is all variables, and domain is each possible assignment (For each assignment create a constraint). This ensures that all values are assigned when set to have an upper and lower bound of 1.We can use use
Neq
constraint with a bit of modification to ensure the correct sequencing by feeding it tuples of valid assignments.We can again use
NValues
constraint to ensure thek_assignment
requirement by passing a lower bound of 1, and upper bound ofK
with domainK_assignments
.In the same way we can use
NValues
constraint with domainproblem.first_assignments()
for the first assignment. And another with domainproblem.valid_assignments()
to fill in the blanks.
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
We can use an
NValues
constraint whose scope is all variables, and domain is each possible assignment (For each assignment create a constraint). This ensures that all values are assigned when set to have an upper and lower bound of 1.We can use use
Neq
constraint with a bit of modification to ensure the correct sequencing by feeding it tuples of valid assignments.We can again use
NValues
constraint to ensure thek_assignment
requirement by passing a lower bound of 1, and upper bound ofK
with domainK_assignments
.In the same way we can use
NValues
constraint with domainproblem.first_assignments()
for the first assignment. And another with domainproblem.valid_assignments()
to fill in the blanks.
add a comment |
up vote
1
down vote
accepted
We can use an
NValues
constraint whose scope is all variables, and domain is each possible assignment (For each assignment create a constraint). This ensures that all values are assigned when set to have an upper and lower bound of 1.We can use use
Neq
constraint with a bit of modification to ensure the correct sequencing by feeding it tuples of valid assignments.We can again use
NValues
constraint to ensure thek_assignment
requirement by passing a lower bound of 1, and upper bound ofK
with domainK_assignments
.In the same way we can use
NValues
constraint with domainproblem.first_assignments()
for the first assignment. And another with domainproblem.valid_assignments()
to fill in the blanks.
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
We can use an
NValues
constraint whose scope is all variables, and domain is each possible assignment (For each assignment create a constraint). This ensures that all values are assigned when set to have an upper and lower bound of 1.We can use use
Neq
constraint with a bit of modification to ensure the correct sequencing by feeding it tuples of valid assignments.We can again use
NValues
constraint to ensure thek_assignment
requirement by passing a lower bound of 1, and upper bound ofK
with domainK_assignments
.In the same way we can use
NValues
constraint with domainproblem.first_assignments()
for the first assignment. And another with domainproblem.valid_assignments()
to fill in the blanks.
We can use an
NValues
constraint whose scope is all variables, and domain is each possible assignment (For each assignment create a constraint). This ensures that all values are assigned when set to have an upper and lower bound of 1.We can use use
Neq
constraint with a bit of modification to ensure the correct sequencing by feeding it tuples of valid assignments.We can again use
NValues
constraint to ensure thek_assignment
requirement by passing a lower bound of 1, and upper bound ofK
with domainK_assignments
.In the same way we can use
NValues
constraint with domainproblem.first_assignments()
for the first assignment. And another with domainproblem.valid_assignments()
to fill in the blanks.
answered Nov 16 at 19:20
Ge0rges
1,0551025
1,0551025
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53244153%2fconstraint-satisfaction-problem-formulation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
– Michael Veksler
Nov 11 at 12:46
Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
– Michael Veksler
Nov 11 at 12:49
Please seed my latest edit for clarifications. @MichaelVeksler
– Ge0rges
Nov 11 at 20:57
If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
– Michael Veksler
Nov 11 at 21:05
No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
– Ge0rges
Nov 11 at 21:12