Lab 3: Constraint Satisfaction
From 6.034 Wiki
(formatting, mostly removing extraneous html tags) |
|||
Line 18: | Line 18: | ||
=== Setting up a Constraint Satisfaction Problem === | === Setting up a Constraint Satisfaction Problem === | ||
<div class="outline-text-3" id="text-1-1"> | <div class="outline-text-3" id="text-1-1"> | ||
- | + | ||
Before beginning, you may want to familiarize yourself with the | Before beginning, you may want to familiarize yourself with the | ||
following terms: variable, value, domain, constraint, assignment. | following terms: variable, value, domain, constraint, assignment. | ||
- | |||
- | |||
Here is a problem that can be solved using constrained search: | Here is a problem that can be solved using constrained search: | ||
- | + | ||
<blockquote> | <blockquote> | ||
- | + | ||
[e.g. insert the Pokemon problem here] todo | [e.g. insert the Pokemon problem here] todo | ||
The Pokemon problem is in sample_csp.py. | The Pokemon problem is in sample_csp.py. | ||
- | + | ||
</blockquote> | </blockquote> | ||
- | + | ||
This part of the lab will show you how to convert this problem into a | This part of the lab will show you how to convert this problem into a | ||
<code>ConstraintSatisfactionProblem</code> instance using our constraint | <code>ConstraintSatisfactionProblem</code> instance using our constraint | ||
satisfaction API. The complete documentation is here: <a href="#sec-2">API Reference Documentation</a>. | satisfaction API. The complete documentation is here: <a href="#sec-2">API Reference Documentation</a>. | ||
- | |||
- | |||
This problem requires two kinds of constraint: a must-be-equal | This problem requires two kinds of constraint: a must-be-equal | ||
constraint and a must-not-be-equal constraint. In this lab, | constraint and a must-not-be-equal constraint. In this lab, | ||
Line 47: | Line 43: | ||
variables as arguments and return True or False based on whether the | variables as arguments and return True or False based on whether the | ||
constraint is satisfied or not. | constraint is satisfied or not. | ||
- | |||
- | |||
Here are definitions for the must-be-equal and must-not-be-equal | Here are definitions for the must-be-equal and must-not-be-equal | ||
constraint functions. (These are defined in constraint_api.py.) | constraint functions. (These are defined in constraint_api.py.) | ||
- | |||
- | |||
def constraint_equal(a,b) : | def constraint_equal(a,b) : | ||
Line 61: | Line 53: | ||
return a != b | return a != b | ||
- | |||
- | |||
To set up the problem, we first establish a new | To set up the problem, we first establish a new | ||
<code>ConstraintSatisfactionProblem</code> instance. There are five variables | <code>ConstraintSatisfactionProblem</code> instance. There are five variables | ||
- | which we pass an an argument in a list | + | which we pass an an argument in a list — the five questions to be answered. |
- | + | ||
- | + | ||
- | + | ||
<pre class="src src-python" id="example-setup-vars">pokemon_problem = ConstraintSatisfactionProblem(["Q1","Q2","Q3","Q4","Q5"]) | <pre class="src src-python" id="example-setup-vars">pokemon_problem = ConstraintSatisfactionProblem(["Q1","Q2","Q3","Q4","Q5"]) | ||
</pre> | </pre> | ||
- | |||
- | |||
Here, we specify the values in each variable's domain. | Here, we specify the values in each variable's domain. | ||
- | |||
- | |||
<pre class="src src-python" id="example-setup-domains">pokemon_problem.set_domain("Q1",["A","B","C","D","E"]) | <pre class="src src-python" id="example-setup-domains">pokemon_problem.set_domain("Q1",["A","B","C","D","E"]) | ||
Line 85: | Line 68: | ||
pokemon_problem.set_domain("Q5",["A","B","C","D","E"]) | pokemon_problem.set_domain("Q5",["A","B","C","D","E"]) | ||
</pre> | </pre> | ||
- | |||
- | |||
- | |||
Next, we set up constraints. Each constraint takes two variable names, | Next, we set up constraints. Each constraint takes two variable names, | ||
and a binary predicate. (For more details on the binary predicate, | and a binary predicate. (For more details on the binary predicate, | ||
see the API Reference Documentation.) | see the API Reference Documentation.) | ||
- | |||
- | |||
- | |||
<pre class="src src-python">pokemon_problem.add_constraint("Q1","Q4", constraint_different) | <pre class="src src-python">pokemon_problem.add_constraint("Q1","Q4", constraint_different) | ||
Line 105: | Line 82: | ||
pokemon_problem.add_constraint("Q4","Q5", constraint_equal) | pokemon_problem.add_constraint("Q4","Q5", constraint_equal) | ||
</pre> | </pre> | ||
- | |||
- | |||
- | |||
Finally, <code>csp.init_unassigned_vars</code> tells the problem which variables need | Finally, <code>csp.init_unassigned_vars</code> tells the problem which variables need | ||
to be assigned and in what order. If passed no argument, it simply | to be assigned and in what order. If passed no argument, it simply | ||
includes all of the variables in the problem in some arbitrary order. | includes all of the variables in the problem in some arbitrary order. | ||
- | |||
- | |||
- | |||
<pre class="src src-python">pokemon_problem.init_unassigned_vars() | <pre class="src src-python">pokemon_problem.init_unassigned_vars() | ||
</pre> | </pre> | ||
- | |||
- | |||
Alternatively, you can also pass an argument to specify the order of the unassigned_vars yourself: | Alternatively, you can also pass an argument to specify the order of the unassigned_vars yourself: | ||
- | |||
- | |||
- | |||
<pre class="src src-python"># (An alternative, which we won't use here.) | <pre class="src src-python"># (An alternative, which we won't use here.) | ||
pokemon_problem.init_unassigned_vars(["Q4","Q2","Q3","Q1","Q5"]) | pokemon_problem.init_unassigned_vars(["Q4","Q2","Q3","Q1","Q5"]) | ||
</pre> | </pre> | ||
- | + | ||
- | + | ||
(For some problems, efficiently re-ordering of the variables can make | (For some problems, efficiently re-ordering of the variables can make | ||
a large difference in performance.) | a large difference in performance.) | ||
- | |||
- | |||
- | |||
- | |||
We have set up the variables, the domains, and the constraints. This | We have set up the variables, the domains, and the constraints. This | ||
- | problem is now ready to be solved | + | problem is now ready to be solved — all we need is a CSP solver. |
- | + | ||
- | + | ||
- | + | ||
+ | === Writing a depth-first search solver === | ||
- | |||
- | |||
- | |||
- | |||
Please write a constraint solver that uses <b>depth-first search</b> to | Please write a constraint solver that uses <b>depth-first search</b> to | ||
find a solution. | find a solution. | ||
- | |||
- | |||
- | |||
<pre class="src src-python">def solve_constraint_dfs(csp) : | <pre class="src src-python">def solve_constraint_dfs(csp) : | ||
raise NotImplementedError | raise NotImplementedError | ||
</pre> | </pre> | ||
- | |||
- | |||
- | |||
Hint: This is exactly depth-first search as in the search lab, but | Hint: This is exactly depth-first search as in the search lab, but | ||
this time the items in the agenda are partially-solved problems, not | this time the items in the agenda are partially-solved problems, not | ||
paths. | paths. | ||
- | |||
- | |||
- | |||
- | |||
- | |||
Here is a rough outline of how to proceed: | Here is a rough outline of how to proceed: | ||
- | |||
<ol class="org-ol"> | <ol class="org-ol"> | ||
- | <li | + | <li> |
Create an agenda containing only the problem <code>csp</code>. | Create an agenda containing only the problem <code>csp</code>. | ||
- | + | ||
</li> | </li> | ||
- | <li | + | <li> |
Until the agenda is empty, pop the first problem off the list. | Until the agenda is empty, pop the first problem off the list. | ||
- | + | ||
</li> | </li> | ||
- | <li | + | <li> |
For that problem, check all the constraints between the variables | For that problem, check all the constraints between the variables | ||
that have been assigned values so far. If any constraint is | that have been assigned values so far. If any constraint is | ||
Line 190: | Line 133: | ||
loop. (The addition of this constraint-checking step is | loop. (The addition of this constraint-checking step is | ||
where constrained search differs from ordinary search.) | where constrained search differs from ordinary search.) | ||
- | + | ||
</li> | </li> | ||
- | <li | + | <li> |
If none of the constraints have been violated, check whether the | If none of the constraints have been violated, check whether the | ||
problem has any unassigned variables (<code>csp.unassigned_vars</code>). If | problem has any unassigned variables (<code>csp.unassigned_vars</code>). If | ||
Line 208: | Line 151: | ||
and final csp (which has all vars assigned) | and final csp (which has all vars assigned) | ||
- | |||
</li> | </li> | ||
- | <li | + | <li> |
If the problem has some unassigned variables: | If the problem has some unassigned variables: | ||
- | + | ||
<ul class="org-ul"> | <ul class="org-ul"> | ||
<li>Take the first unassigned variable off the list | <li>Take the first unassigned variable off the list | ||
Line 230: | Line 172: | ||
</ol> | </ol> | ||
- | + | These are helper functions that you can use within <code>solve_constraint_dfs</code>. | |
- | + | ||
- | These are helper functions that you can use within | + | |
- | <code>solve_constraint_dfs</code>. | + | |
def has_empty_domains(csp): #todo format | def has_empty_domains(csp): #todo format | ||
"Returns True if csp has one or more empty domains, otherwise False" | "Returns True if csp has one or more empty domains, otherwise False" | ||
return not all(csp.domains.values()) | return not all(csp.domains.values()) | ||
- | |||
check_all_assignments should return False if the problem's | check_all_assignments should return False if the problem's | ||
assigned values violate some constraint, otherwise True. | assigned values violate some constraint, otherwise True. | ||
- | |||
- | |||
- | |||
<pre class="src src-python">def check_all_assignments(problem) : | <pre class="src src-python">def check_all_assignments(problem) : | ||
- | |||
</pre> | </pre> | ||
- | |||
- | |||
- | |||
+ | === Domain reduction before search === | ||
- | |||
- | |||
- | |||
- | |||
Domain reduction is a strategy for eliminating impossible values in | Domain reduction is a strategy for eliminating impossible values in | ||
advance to cut down on the amount of search you have to do. | advance to cut down on the amount of search you have to do. | ||
- | |||
- | |||
First, write a helper function to eliminate values from a variable's neighbors' domains. | First, write a helper function to eliminate values from a variable's neighbors' domains. | ||
- | Each variable should | + | Each variable should appear AT MOST ONCE in the list; the list should contain no duplicates. |
- | appear AT MOST ONCE in the list; the list should | + | |
- | contain no duplicates. | + | |
- | + | ||
- | |||
Hint: csp.constraints_between may help. | Hint: csp.constraints_between may help. | ||
- | |||
def eliminate_from_neighbors(csp, var) : #todo format (move docstring up to description) | def eliminate_from_neighbors(csp, var) : #todo format (move docstring up to description) | ||
Line 280: | Line 201: | ||
reduced to size 0, quits and returns None.""" | reduced to size 0, quits and returns None.""" | ||
- | |||
Next, you will need to write a domain-reduction algorithm. | Next, you will need to write a domain-reduction algorithm. | ||
- | |||
- | |||
- | |||
<pre class="src src-python">def domain_reduction(csp, queue=None) : | <pre class="src src-python">def domain_reduction(csp, queue=None) : | ||
raise NotImplementedError | raise NotImplementedError | ||
</pre> | </pre> | ||
- | |||
- | |||
Here is a rough description of the domain reduction algorithm: | Here is a rough description of the domain reduction algorithm: | ||
- | + | ||
<ol class="org-ol"> | <ol class="org-ol"> | ||
- | <li>Establish a queue | + | <li>Establish a queue — if the optional argument <code>queue</code> was passed |
as an argument, use that as your queue. Otherwise, <code>queue</code> should | as an argument, use that as your queue. Otherwise, <code>queue</code> should | ||
consist of all the variables in the problem. | consist of all the variables in the problem. | ||
Line 322: | Line 237: | ||
</li> | </li> | ||
</ol> | </ol> | ||
- | + | ||
Hint: You can remove values from a variable's domain using <code>csp.eliminate(var, val)</code>. | Hint: You can remove values from a variable's domain using <code>csp.eliminate(var, val)</code>. | ||
(But don't eliminate values from a variable while iterating over its domain, or Python will get confused.) | (But don't eliminate values from a variable while iterating over its domain, or Python will get confused.) | ||
- | < | + | <h4 id="sec-1-3-1"> Benchmarks</h4> |
- | </ | + | |
- | |||
- | |||
- | |||
- | |||
- | |||
You can solve the pokemon problem by calling | You can solve the pokemon problem by calling | ||
<code>solve_constraint_dfs(pokemon_problem)</code> directly. Using domain | <code>solve_constraint_dfs(pokemon_problem)</code> directly. Using domain | ||
reduction first, however, should make search faster. Please answer the | reduction first, however, should make search faster. Please answer the | ||
following questions in your lab file: | following questions in your lab file: | ||
- | |||
- | |||
- | |||
- | + | QUESTION 1: How many extensions does it take to solve the Pokemon problem #todo format | |
- | + | with dfs if you DON'T use domain reduction before solving it? | |
- | + | Hint: Use get_pokemon_problem() to get a new copy of the Pokemon problem | |
+ | each time you want to solve it with a different search method. | ||
- | + | ANSWER_1 = None | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
+ | QUESTION 2: How many extensions does it take to solve the Pokemon problem | ||
+ | with dfs if you DO use domain reduction before solving it? | ||
- | + | ANSWER_2 = None | |
=== Propagation through reduced domains === | === Propagation through reduced domains === | ||
- | |||
- | |||
Domain reduction can be used not only before search, but also <i>during</i> | Domain reduction can be used not only before search, but also <i>during</i> | ||
search. When used during search, domain reduction can make use of the | search. When used during search, domain reduction can make use of the | ||
Line 367: | Line 268: | ||
result is a new, faster, csp solution method: propagation through | result is a new, faster, csp solution method: propagation through | ||
reduced domains. | reduced domains. | ||
- | |||
- | |||
- | |||
<pre class="src src-python">def solve_constraint_propagate_reduced_domains(problem) : | <pre class="src src-python">def solve_constraint_propagate_reduced_domains(problem) : | ||
raise NotImplementedError | raise NotImplementedError | ||
</pre> | </pre> | ||
- | |||
- | |||
You can reuse most of your code from your solve_constraint_dfs | You can reuse most of your code from your solve_constraint_dfs | ||
algorithm, as domain reduction adds only a single conditional | algorithm, as domain reduction adds only a single conditional | ||
Line 382: | Line 278: | ||
your <code>domain_reduction</code> function with the assigned variable | your <code>domain_reduction</code> function with the assigned variable | ||
as an argument. If the <code>domain_reduction</code> function returns | as an argument. If the <code>domain_reduction</code> function returns | ||
- | <code>None</code>, the problem can't be solved with the given assignments | + | <code>None</code>, the problem can't be solved with the given assignments — |
don't add the problem to the agenda. Otherwise, add the problem to the | don't add the problem to the agenda. Otherwise, add the problem to the | ||
agenda as usual. | agenda as usual. | ||
- | |||
Note: domain_reduction should remove values from the assigned variable's ''neighbors' ''domains, not from the variable's domain. | Note: domain_reduction should remove values from the assigned variable's ''neighbors' ''domains, not from the variable's domain. | ||
- | |||
- | |||
- | |||
Answer the following question in your lab4.py file: | Answer the following question in your lab4.py file: | ||
- | + | QUESTION 3: How many extensions does it take to solve the Pokemon problem | |
- | + | with propagation through reduced domains? (Don't use domain reduction before solving it.) | |
- | + | ||
- | + | ||
- | + | ||
- | + | ANSWER_3 = None | |
=== Propagation through singleton domains === | === Propagation through singleton domains === | ||
- | |||
- | |||
The <code>reduce_domains</code> procedure is comprehensive, but expensive: it | The <code>reduce_domains</code> procedure is comprehensive, but expensive: it | ||
eliminates as many values as possible, but it continually adds more | eliminates as many values as possible, but it continually adds more | ||
Line 410: | Line 297: | ||
use <i>before</i> solving a constraint satisfaction problem, but is often | use <i>before</i> solving a constraint satisfaction problem, but is often | ||
too expensive to call repeatedly during search. | too expensive to call repeatedly during search. | ||
- | |||
- | |||
Instead of comprehensively reducing all the domains in a problem, as | Instead of comprehensively reducing all the domains in a problem, as | ||
<code>reduce_domains</code> does, you can instead reduce only <i>some</i> of the | <code>reduce_domains</code> does, you can instead reduce only <i>some</i> of the | ||
- | domains. This results in <i>propagation through singleton domains</i> | + | domains. This results in <i>propagation through singleton domains</i> — a |
reduction algorithm which does not detect as many dead ends, but which | reduction algorithm which does not detect as many dead ends, but which | ||
is significantly faster. | is significantly faster. | ||
- | |||
- | |||
- | |||
<pre class="src src-python">def domain_reduction_singleton_domains(csp, queue=None) : | <pre class="src src-python">def domain_reduction_singleton_domains(csp, queue=None) : | ||
- | |||
</pre> | </pre> | ||
- | |||
- | |||
Propagation through singletons is like propagation through reduced | Propagation through singletons is like propagation through reduced | ||
- | domains, except that variables must pass a test in order to be added | + | domains, except that variables must pass a test in order to be added to the queue: |
- | to the queue: | + | |
- | + | ||
<blockquote> | <blockquote> | ||
- | |||
In propagation through singleton domains, you only append a variable | In propagation through singleton domains, you only append a variable | ||
to the queue if it has exactly one value left in its domain. | to the queue if it has exactly one value left in its domain. | ||
- | |||
</blockquote> | </blockquote> | ||
- | |||
<b>Common misconception</b>: Please note that propagation never <i>assigns</i> | <b>Common misconception</b>: Please note that propagation never <i>assigns</i> | ||
values to variables; it only eliminates values. There is a distinction | values to variables; it only eliminates values. There is a distinction | ||
Line 446: | Line 320: | ||
variables: a variable can have one value in its domain without any | variables: a variable can have one value in its domain without any | ||
value being assigned yet. | value being assigned yet. | ||
- | |||
- | |||
- | |||
Then write: | Then write: | ||
Line 458: | Line 329: | ||
raise NotImplementedError | raise NotImplementedError | ||
- | + | Answer the following question in your lab4.py file: | |
- | + | QUESTION 4: How many extensions does it take to solve the Pokemon problem | |
- | + | with propagation through singleton domains? (Don't use domain reduction before solving it.) | |
- | + | ||
- | ANSWER_4 = None | + | ANSWER_4 = None |
- | + | ||
- | + | ||
=== Forward checking === | === Forward checking === | ||
- | |||
- | |||
Forward checking is even more restrictive than propagation through | Forward checking is even more restrictive than propagation through | ||
singletons: it <i>never</i> adds variables to the queue. (Later in this | singletons: it <i>never</i> adds variables to the queue. (Later in this | ||
Line 476: | Line 342: | ||
performs best in terms of tradeoffs between performance and | performs best in terms of tradeoffs between performance and | ||
comprehensiveness.) | comprehensiveness.) | ||
- | |||
- | |||
Instead of patterning our forward checking algorithm off of | Instead of patterning our forward checking algorithm off of | ||
<code>domain_reduction</code> again, we'll write a fully general algorithm called | <code>domain_reduction</code> again, we'll write a fully general algorithm called | ||
Line 484: | Line 348: | ||
seen: propagation through reduced domains, propagation through | seen: propagation through reduced domains, propagation through | ||
singletons, and forward checking. | singletons, and forward checking. | ||
- | |||
- | |||
The function <code>propagate</code> will be similar to the propagation algorithms | The function <code>propagate</code> will be similar to the propagation algorithms | ||
you've already defined. The difference is that it will take an | you've already defined. The difference is that it will take an | ||
Line 494: | Line 356: | ||
. If the function returns <code>True</code>, it should add the variable to the | . If the function returns <code>True</code>, it should add the variable to the | ||
queue. Otherwise, it shouldn't. | queue. Otherwise, it shouldn't. | ||
- | |||
- | |||
- | |||
<pre class="src src-python">def propagate(enqueue_condition_fn, csp, queue = None) : | <pre class="src src-python">def propagate(enqueue_condition_fn, csp, queue = None) : | ||
raise NotImplementedError | raise NotImplementedError | ||
</pre> | </pre> | ||
- | |||
- | |||
To review, the three enqueueing conditions we've seen are: | To review, the three enqueueing conditions we've seen are: | ||
- | + | ||
<dl class="org-dl"> | <dl class="org-dl"> | ||
<dt>domain reduction</dt><dd>always add the variable to the queue | <dt>domain reduction</dt><dd>always add the variable to the queue | ||
Line 516: | Line 373: | ||
</dl> | </dl> | ||
- | |||
Write functions for each of these tests. Hint: some of these | Write functions for each of these tests. Hint: some of these | ||
functions may ignore some of their arguments. | functions may ignore some of their arguments. | ||
- | |||
- | |||
- | |||
<pre class="src src-python">def condition_domain_reduction(csp, var) : | <pre class="src src-python">def condition_domain_reduction(csp, var) : | ||
- | |||
def condition_singleton(csp, var) : | def condition_singleton(csp, var) : | ||
- | |||
def condition_forward_checking(csp, var) : | def condition_forward_checking(csp, var) : | ||
- | |||
</pre> | </pre> | ||
- | |||
- | |||
And thus we can define: | And thus we can define: | ||
- | |||
- | |||
<pre class="src src-python">domain_reduction_forward_checking = | <pre class="src src-python">domain_reduction_forward_checking = | ||
lambda csp, queue=None: propagate(condition_forward_checking, csp, queue) | lambda csp, queue=None: propagate(condition_forward_checking, csp, queue) | ||
</pre> | </pre> | ||
- | |||
- | |||
- | |||
- | |||
=== A generic CSP solver === | === A generic CSP solver === | ||
- | |||
- | |||
Write an algorithm that can solve a problem using any enqueueing | Write an algorithm that can solve a problem using any enqueueing | ||
strategy. As a special case, if the enqueue_condition is <code>None</code>, don't | strategy. As a special case, if the enqueue_condition is <code>None</code>, don't | ||
use any propagation at all (i.e. the algorithm should perform only | use any propagation at all (i.e. the algorithm should perform only | ||
depth-first search in this case.) | depth-first search in this case.) | ||
- | |||
- | |||
- | |||
<pre class="src src-python">def solve_constraint_generic(problem, enqueue_condition=None) : | <pre class="src src-python">def solve_constraint_generic(problem, enqueue_condition=None) : | ||
- | |||
</pre> | </pre> | ||
- | |||
- | |||
"""Solves the problem, calling propagate with the specified enqueue #todo formatting | """Solves the problem, calling propagate with the specified enqueue #todo formatting | ||
Line 568: | Line 402: | ||
Same return type as solve_constraint_dfs.""" | Same return type as solve_constraint_dfs.""" | ||
- | Answer: | + | Answer the following question in your lab4.py file: |
- | + | QUESTION 5: How many extensions does it take to solve the Pokemon problem #todo formatting | |
- | + | with DFS and forward checking, but no propagation? (Don't use domain reduction before solving it.) | |
- | + | ||
- | ANSWER_5 = None | + | ANSWER_5 = None |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
=== Solving your own CSPs === | === Solving your own CSPs === | ||
- | |||
- | |||
<h4 id="sec-1-8-1"> Defining new constraints</h4> | <h4 id="sec-1-8-1"> Defining new constraints</h4> | ||
- | + | ||
- | + | ||
Assuming m and n are integers, write a function that returns True if | Assuming m and n are integers, write a function that returns True if | ||
m and n are adjacent values (i.e. if they differ by exactly one) and | m and n are adjacent values (i.e. if they differ by exactly one) and | ||
False otherwise. | False otherwise. | ||
- | + | ||
<div class="org-src-container"> | <div class="org-src-container"> | ||
Line 631: | Line 424: | ||
</div> | </div> | ||
- | + | ||
Also write one for being non-adjacent. There are trivial ways to do | Also write one for being non-adjacent. There are trivial ways to do | ||
it; feel free to call <code>constraint_adjacent</code>. | it; feel free to call <code>constraint_adjacent</code>. | ||
- | + | ||
<div class="org-src-container"> | <div class="org-src-container"> | ||
Line 644: | Line 437: | ||
- | + | ||
The following example shows how you build a constraint object that | The following example shows how you build a constraint object that | ||
- | requires two variables | + | requires two variables — call them A and B — to be different. |
- | + | ||
<div class="org-src-container"> | <div class="org-src-container"> | ||
Line 655: | Line 448: | ||
</div> | </div> | ||
- | + | ||
Some constraint problems include a constraint that requires all of | Some constraint problems include a constraint that requires all of | ||
the variables to be different from one another. It can be tedious to | the variables to be different from one another. It can be tedious to | ||
Line 665: | Line 458: | ||
so you don't need to produce two different constraints for (A,B) and | so you don't need to produce two different constraints for (A,B) and | ||
(B,A). | (B,A). | ||
- | + | ||
specifically, do not duplicate constraints #todo incorporate above | specifically, do not duplicate constraints #todo incorporate above | ||
Line 681: | Line 474: | ||
<h4 id="sec-1-8-2"> Defining a new problem: Moose problem (OPTIONAL)</h4> | <h4 id="sec-1-8-2"> Defining a new problem: Moose problem (OPTIONAL)</h4> | ||
<div class="outline-text-4" id="text-1-8-2"> | <div class="outline-text-4" id="text-1-8-2"> | ||
- | + | ||
If you want to try out your new constraints and CSP solver, you may design and solve a constraint satisfaction problem for the Moose Problem from 2008 Quiz 2. You are of course welcome to implement additional problems; some of our favorites include the Time Travelers problem (2009 Quiz 2) and the Zoo problem (2011 Quiz 2). | If you want to try out your new constraints and CSP solver, you may design and solve a constraint satisfaction problem for the Moose Problem from 2008 Quiz 2. You are of course welcome to implement additional problems; some of our favorites include the Time Travelers problem (2009 Quiz 2) and the Zoo problem (2011 Quiz 2). | ||
- | + | ||
todo: insert description of moose problem, using people as variables and seats as values | todo: insert description of moose problem, using people as variables and seats as values | ||
Line 690: | Line 483: | ||
- | + | ||
Interpret constraints that only mention one person (e.g. "McCain ...[todo]... seat 1") as an indication that you should | Interpret constraints that only mention one person (e.g. "McCain ...[todo]... seat 1") as an indication that you should | ||
leave out those values from the variable's domain; you won't | leave out those values from the variable's domain; you won't | ||
need to make a Constraint to represent those kinds of constraints. | need to make a Constraint to represent those kinds of constraints. | ||
- | |||
- | + | ||
+ | |||
Establish the domains of the variables. Each variable will have a | Establish the domains of the variables. Each variable will have a | ||
domain that's a subset of [1,2,3,4,5,6]. | domain that's a subset of [1,2,3,4,5,6]. | ||
- | |||
- | + | ||
+ | |||
Establish the constraints. Remember the constraint that says that | Establish the constraints. Remember the constraint that says that | ||
all of the variables must be assigned a different value. You may | all of the variables must be assigned a different value. You may | ||
want to use <code>csp.add_constraints(list)</code>. | want to use <code>csp.add_constraints(list)</code>. | ||
- | + | ||
</div> | </div> | ||
</div> | </div> | ||
Line 720: | Line 513: | ||
=== TODO Counting solutions === | === TODO Counting solutions === | ||
Use "yield" to count the number of solutions. | Use "yield" to count the number of solutions. | ||
+ | |||
+ | <h4 id="sec-1-7-1"> TODO Comparing propagation strategies</h4> | ||
+ | <div class="outline-text-4" id="text-1-7-1"> | ||
+ | |||
+ | Including the trouble with texas. | ||
+ | |||
+ | </div> | ||
+ | </div> | ||
+ | |||
+ | <div id="outline-container-sec-1-7-2" class="outline-4"> | ||
+ | <h4 id="sec-1-7-2"> TODO Variable re-ordering</h4> | ||
+ | <div class="outline-text-4" id="text-1-7-2"> | ||
+ | |||
+ | How should you order your variables in the agenda? e.g. | ||
+ | |||
+ | <ul class="org-ul"> | ||
+ | <li>most constrained variables first | ||
+ | </li> | ||
+ | <li>smallest domains first | ||
+ | </li> | ||
+ | </ul> | ||
+ | |||
+ | |||
+ | Let's find out empirically. | ||
--> | --> | ||
== API Reference Documentation == | == API Reference Documentation == | ||
<div class="outline-text-2" id="text-2"> | <div class="outline-text-2" id="text-2"> | ||
- | + | ||
In this lab, we provide an API for representing and | In this lab, we provide an API for representing and | ||
manipulating partial solutions to constraint satisfaction problems. | manipulating partial solutions to constraint satisfaction problems. | ||
Line 733: | Line 550: | ||
!--> | !--> | ||
- | + | ||
</div> | </div> | ||
Line 740: | Line 557: | ||
=== Constraint Satisfaction Problems === | === Constraint Satisfaction Problems === | ||
<div class="outline-text-3" id="text-2-1"> | <div class="outline-text-3" id="text-2-1"> | ||
- | + | ||
A <code>ConstraintSatisfactionProblem</code> is an object representing a | A <code>ConstraintSatisfactionProblem</code> is an object representing a | ||
partially-solved constraint satisfaction problem. Its fields are: | partially-solved constraint satisfaction problem. Its fields are: | ||
- | + | ||
Line 768: | Line 585: | ||
</ul> | </ul> | ||
- | + | ||
Please note that while you may <i>read</i> any of the above variables, you | Please note that while you may <i>read</i> any of the above variables, you | ||
should probably not modify them directly; instead, you should use the | should probably not modify them directly; instead, you should use the | ||
following API methods. (Below, <code>csp</code> stands for some | following API methods. (Below, <code>csp</code> stands for some | ||
<code>ConstraintSatisfactionProblem</code> instance that you want to manipulate.) | <code>ConstraintSatisfactionProblem</code> instance that you want to manipulate.) | ||
- | + | ||
<ul> | <ul> | ||
Line 804: | Line 621: | ||
<ul> | <ul> | ||
- | <li><tt>'''csp'''.constraints_between(var1, var2)</tt> <span></span | + | <li><tt>'''csp'''.constraints_between(var1, var2)</tt> <span></span> |
Return a list of all the | Return a list of all the | ||
constraints between var1 and var2. Arguments that are <code>None</code> will | constraints between var1 and var2. Arguments that are <code>None</code> will | ||
Line 811: | Line 628: | ||
<code>constraints_between(None, None)</code> will return all of the | <code>constraints_between(None, None)</code> will return all of the | ||
constraints in the problem. | constraints in the problem. | ||
- | |||
- | + | ||
+ | |||
! Please note that for your convenience, the constraints returned | ! Please note that for your convenience, the constraints returned | ||
will always be altered to match the order of the arguments you | will always be altered to match the order of the arguments you | ||
passed to this method. For example, | passed to this method. For example, | ||
<code>csp.constraints_between(None, 'Y')</code> will return a list of all | <code>csp.constraints_between(None, 'Y')</code> will return a list of all | ||
- | constraints involving 'Y' | + | constraints involving 'Y' — and the constraints will be altered |
so that 'Y' is their <i>second</i> variable (<code>var2</code>) in every case. | so that 'Y' is their <i>second</i> variable (<code>var2</code>) in every case. | ||
- | + | ||
</li> | </li> | ||
- | <li><tt>'''csp'''.add_constraint(var1, var2, test_fn)</tt> <span></span | + | <li><tt>'''csp'''.add_constraint(var1, var2, test_fn)</tt> <span></span> |
Takes two variables and a | Takes two variables and a | ||
function to act as a constraint between them, creating a | function to act as a constraint between them, creating a | ||
<code>Constraint</code> object and adding it to the list | <code>Constraint</code> object and adding it to the list | ||
<code>csp.constraints</code>. | <code>csp.constraints</code>. | ||
- | |||
- | + | ||
- | The function <code>test_fn</code> must take two arguments | + | |
- | the first variable, and a value for the second variable | + | The function <code>test_fn</code> must take two arguments — a value for |
+ | the first variable, and a value for the second variable — and | ||
return <code>True</code> if the values satisfy the constraint, or <code>False</code> | return <code>True</code> if the values satisfy the constraint, or <code>False</code> | ||
otherwise. | otherwise. | ||
- | + | ||
</li> | </li> | ||
- | <li><tt>'''csp'''.add_constraints(constraint_list)</tt> <span></span | + | <li><tt>'''csp'''.add_constraints(constraint_list)</tt> <span></span> |
Add a list of <code>Constraint</code> | Add a list of <code>Constraint</code> | ||
objects to the list <code>csp.constraints</code>. Useful for when you want | objects to the list <code>csp.constraints</code>. Useful for when you want | ||
to add several constraints to the problem at once, rather than | to add several constraints to the problem at once, rather than | ||
one at a time using <code>csp.add_constraint</code>. | one at a time using <code>csp.add_constraint</code>. | ||
- | + | ||
</li> | </li> | ||
</ul> | </ul> | ||
Line 848: | Line 665: | ||
- | <!-- TODO: I removed the copy function from the API | + | <!-- TODO: I removed the copy function from the API <- ??? -jmn |
<ul> | <ul> | ||
<li><tt>'''csp'''.copy()</tt> <span></span>Return a (deep) copy of this constraint satisfaction | <li><tt>'''csp'''.copy()</tt> <span></span>Return a (deep) copy of this constraint satisfaction | ||
Line 864: | Line 681: | ||
=== Constraints === | === Constraints === | ||
<div class="outline-text-3" id="text-2-2"> | <div class="outline-text-3" id="text-2-2"> | ||
- | + | ||
- | A <code>Constraint</code> is a fairly basic object. It has three | + | A <code>Constraint</code> is a fairly basic object. It has three variables— |
- | <code>var1</code>, <code>var2</code>, and <code>constraint_fn</code> | + | <code>var1</code>, <code>var2</code>, and <code>constraint_fn</code> — and one method, <code>check(val1, |
val2)</code>. | val2)</code>. | ||
- | |||
- | + | ||
+ | |||
<code>const.check(val1, val2)</code> simply applies the <code>Constraint</code>'s | <code>const.check(val1, val2)</code> simply applies the <code>Constraint</code>'s | ||
constraint function to the two arguments, returning <code>True</code> if the | constraint function to the two arguments, returning <code>True</code> if the | ||
values satisfy the constraint, or <code>False</code> otherwise. | values satisfy the constraint, or <code>False</code> otherwise. | ||
- | + | ||
</div> | </div> | ||
</div> | </div> | ||
Line 890: | Line 707: | ||
<div id="text-footnotes"> | <div id="text-footnotes"> | ||
- | <div class="footdef"><sup><a id="fn.1" class="footnum" href="#fnr.1">1</a></sup | + | <div class="footdef"><sup><a id="fn.1" class="footnum" href="#fnr.1">1</a></sup> Naming the variables may make this easier: you have |
popped Alice off of the queue and are iterating over Alice's | popped Alice off of the queue and are iterating over Alice's | ||
constraints. One of those constraints involves a neighbor, Bob. If | constraints. One of those constraints involves a neighbor, Bob. If | ||
Bob has a value that is incompatible with <i>all</i> of Alice's values, | Bob has a value that is incompatible with <i>all</i> of Alice's values, | ||
- | remove Bob's value and add Bob to the queue. | + | remove Bob's value and add Bob to the queue.</div> |
- | <div class="footdef"><sup><a id="fn.2" class="footnum" href="#fnr.2">2</a></sup | + | <div class="footdef"><sup><a id="fn.2" class="footnum" href="#fnr.2">2</a></sup> Constraint |
satisfaction involves ruling out as many values as | satisfaction involves ruling out as many values as | ||
- | possible in order to limit search. | + | possible in order to limit search.</div> |
- | <div class="footdef"><sup><a id="fn.3" class="footnum" href="#fnr.3">3</a></sup | + | <div class="footdef"><sup><a id="fn.3" class="footnum" href="#fnr.3">3</a></sup> Please note that there is a distinction between |
a variable being assigned a value, and a variable having only one | a variable being assigned a value, and a variable having only one | ||
value left in its domain: a variable can have one value in its | value left in its domain: a variable can have one value in its | ||
- | domain without having an assigned value yet. | + | domain without having an assigned value yet.</div> |
== Survey == | == Survey == | ||
Line 923: | Line 740: | ||
(We'd ask which parts you find confusing, but if you're confused you should really ask a TA.) | (We'd ask which parts you find confusing, but if you're confused you should really ask a TA.) | ||
- | When you're done, run the online tester to submit your code. <!--(The online tester for Lab | + | When you're done, run the online tester to submit your code. <!--(The online tester for Lab 4 will be made available by ___.)--> |
Revision as of 07:07, 9 October 2015
Contents
|
This lab is due by Thursday, October 15 at 10:00pm.
Note: Online tests will be made available shortly. In the meantime, the local tester provides thorough unit tests for each section of the lab.
To work on this lab, you will need to get the code, much like you did for the first two labs.
- You can view the files at: http://web.mit.edu/6.034/www/labs/lab4/
- Download it as a ZIP file: http://web.mit.edu/6.034/www/labs/lab4/lab4.zip
- Or, on Athena, add 6.034 and copy it from /mit/6.034/www/labs/lab4/.
Your answers for this lab belong in the main file lab4.py.
Problems
Setting up a Constraint Satisfaction Problem
Before beginning, you may want to familiarize yourself with the following terms: variable, value, domain, constraint, assignment.
Here is a problem that can be solved using constrained search:
[e.g. insert the Pokemon problem here] todo The Pokemon problem is in sample_csp.py.
This part of the lab will show you how to convert this problem into a
ConstraintSatisfactionProblem
instance using our constraint
satisfaction API. The complete documentation is here: <a href="#sec-2">API Reference Documentation</a>.
This problem requires two kinds of constraint: a must-be-equal constraint and a must-not-be-equal constraint. In this lab, constraints are defined using functions that take the values of two variables as arguments and return True or False based on whether the constraint is satisfied or not.
Here are definitions for the must-be-equal and must-not-be-equal constraint functions. (These are defined in constraint_api.py.)
def constraint_equal(a,b) : return a == b
def constraint_different(a,b) : return a != b
To set up the problem, we first establish a new
ConstraintSatisfactionProblem
instance. There are five variables
which we pass an an argument in a list — the five questions to be answered.
pokemon_problem = ConstraintSatisfactionProblem(["Q1","Q2","Q3","Q4","Q5"])
Here, we specify the values in each variable's domain.
pokemon_problem.set_domain("Q1",["A","B","C","D","E"]) pokemon_problem.set_domain("Q2",["A","B","C","D","E"]) pokemon_problem.set_domain("Q3",["A","B","C","D","E"]) pokemon_problem.set_domain("Q4",["A","B","C","D","E"]) pokemon_problem.set_domain("Q5",["A","B","C","D","E"])
Next, we set up constraints. Each constraint takes two variable names, and a binary predicate. (For more details on the binary predicate, see the API Reference Documentation.)
pokemon_problem.add_constraint("Q1","Q4", constraint_different) pokemon_problem.add_constraint("Q1","Q2", constraint_equal) pokemon_problem.add_constraint("Q3","Q2", constraint_different) pokemon_problem.add_constraint("Q3","Q4", constraint_different) pokemon_problem.add_constraint("Q4","Q5", constraint_equal)
Finally, csp.init_unassigned_vars
tells the problem which variables need
to be assigned and in what order. If passed no argument, it simply
includes all of the variables in the problem in some arbitrary order.
pokemon_problem.init_unassigned_vars()
Alternatively, you can also pass an argument to specify the order of the unassigned_vars yourself:
# (An alternative, which we won't use here.) pokemon_problem.init_unassigned_vars(["Q4","Q2","Q3","Q1","Q5"])
(For some problems, efficiently re-ordering of the variables can make a large difference in performance.)
We have set up the variables, the domains, and the constraints. This problem is now ready to be solved — all we need is a CSP solver.
Writing a depth-first search solver
Please write a constraint solver that uses depth-first search to find a solution.
def solve_constraint_dfs(csp) : raise NotImplementedError
Hint: This is exactly depth-first search as in the search lab, but this time the items in the agenda are partially-solved problems, not paths.
Here is a rough outline of how to proceed:
-
Create an agenda containing only the problem
csp
. - Until the agenda is empty, pop the first problem off the list.
- For that problem, check all the constraints between the variables that have been assigned values so far. If any constraint is violated, the problem cannot be solved with the given assignments; skip the problem and proceed to the next iteration of the loop. (The addition of this constraint-checking step is where constrained search differs from ordinary search.)
-
If none of the constraints have been violated, check whether the
problem has any unassigned variables (
csp.unassigned_vars
). If the problem has no unassigned variables, you've found a complete solution! Return the assignments (csp.assigned_value
). The return type should be a tuple(solution, extension_count)
, containing:- the solution (csp.assigned_value, which is a dictionary mapping variables to assigned values), and
- the number of extensions made (the number of problems popped off the agenda).
-
If the problem has some unassigned variables:
- Take the first unassigned variable off the list (csp.unassigned_vars).
- For each value in the variable's domain (csp.get_domain(var)), create a new copy of the problem. (csp_new = csp.copy()).
- Using the copy, assign the value to the variable. (
csp_new.set_assigned_value(var, val)
). - Collect the list of copies and add the list to the front of the agenda (as is appropriate for depth-first search).
These are helper functions that you can use within solve_constraint_dfs
.
def has_empty_domains(csp): #todo format
"Returns True if csp has one or more empty domains, otherwise False" return not all(csp.domains.values())
check_all_assignments should return False if the problem's assigned values violate some constraint, otherwise True.
def check_all_assignments(problem) :
Domain reduction before search
Domain reduction is a strategy for eliminating impossible values in advance to cut down on the amount of search you have to do.
First, write a helper function to eliminate values from a variable's neighbors' domains. Each variable should appear AT MOST ONCE in the list; the list should contain no duplicates.
Hint: csp.constraints_between may help.
def eliminate_from_neighbors(csp, var) : #todo format (move docstring up to description)
"""Eliminates incompatible values from var's neighbors' domains, modifying the original csp. Returns alphabetically sorted list of the neighboring variables whose domains were reduced, with each variable appearing at most once. If no domains were reduced, returns empty list. If a domain is reduced to size 0, quits and returns None."""
Next, you will need to write a domain-reduction algorithm.
def domain_reduction(csp, queue=None) : raise NotImplementedError
Here is a rough description of the domain reduction algorithm:
- Establish a queue — if the optional argument
queue
was passed as an argument, use that as your queue. Otherwise,queue
should consist of all the variables in the problem. - Until the queue is empty, pop the first variable off the queue.
- Iterate over the variable's constraints: if a neighbor has a value that violates a constraint with every value in the variable's domain, remove the neighbor's value and add the neighbor to the queue if and only if the neighbor is not already in queue<a id="fnr.1" class="footref" href="#fn.1">1</a>.
- If any variable has an empty domain, quit immediately and return None.
- If the queue is empty, domain reduction has finished. As a side-effect, please return: """Uses constraints to reduce domains, modifying the original csp. #todo format If queue is None, initializes propagation queue by adding all variables in alphabetical order. Returns a list of all variables that were dequeued, in the order they were removed from the queue. Variables may appear in the list multiple times. If a domain is reduced to size 0, quits immediately and returns None.""" break any ties lexicographically (probably natural)
Hint: You can remove values from a variable's domain using csp.eliminate(var, val)
.
(But don't eliminate values from a variable while iterating over its domain, or Python will get confused.)
Benchmarks
You can solve the pokemon problem by calling
solve_constraint_dfs(pokemon_problem)
directly. Using domain
reduction first, however, should make search faster. Please answer the
following questions in your lab file:
QUESTION 1: How many extensions does it take to solve the Pokemon problem #todo format
with dfs if you DON'T use domain reduction before solving it?
Hint: Use get_pokemon_problem() to get a new copy of the Pokemon problem each time you want to solve it with a different search method.
ANSWER_1 = None
QUESTION 2: How many extensions does it take to solve the Pokemon problem with dfs if you DO use domain reduction before solving it?
ANSWER_2 = None
Propagation through reduced domains
Domain reduction can be used not only before search, but also during search. When used during search, domain reduction can make use of the assignments you've made to progressively reduce the search space. The result is a new, faster, csp solution method: propagation through reduced domains.
def solve_constraint_propagate_reduced_domains(problem) : raise NotImplementedError
You can reuse most of your code from your solve_constraint_dfs
algorithm, as domain reduction adds only a single conditional
statement: every time you assign a value to a variable, you must call
your domain_reduction
function with the assigned variable
as an argument. If the domain_reduction
function returns
None
, the problem can't be solved with the given assignments —
don't add the problem to the agenda. Otherwise, add the problem to the
agenda as usual.
Note: domain_reduction should remove values from the assigned variable's neighbors' domains, not from the variable's domain.
Answer the following question in your lab4.py file:
QUESTION 3: How many extensions does it take to solve the Pokemon problem with propagation through reduced domains? (Don't use domain reduction before solving it.)
ANSWER_3 = None
Propagation through singleton domains
The reduce_domains
procedure is comprehensive, but expensive: it
eliminates as many values as possible, but it continually adds more
variables to the queue. As a result, it is an effective algorithm to
use before solving a constraint satisfaction problem, but is often
too expensive to call repeatedly during search.
Instead of comprehensively reducing all the domains in a problem, as
reduce_domains
does, you can instead reduce only some of the
domains. This results in propagation through singleton domains — a
reduction algorithm which does not detect as many dead ends, but which
is significantly faster.
def domain_reduction_singleton_domains(csp, queue=None) :
Propagation through singletons is like propagation through reduced domains, except that variables must pass a test in order to be added to the queue:
In propagation through singleton domains, you only append a variable to the queue if it has exactly one value left in its domain.
Common misconception: Please note that propagation never assigns values to variables; it only eliminates values. There is a distinction between variables with one value in their domain, and assigned variables: a variable can have one value in its domain without any value being assigned yet.
Then write:
def solve_constraint_propagate_singleton_domains(problem) : #todo formatting
"""Solves the problem using depth-first search with forward checking and propagation through singleton domains. Same return type as solve_constraint_dfs.""" raise NotImplementedError
Answer the following question in your lab4.py file:
QUESTION 4: How many extensions does it take to solve the Pokemon problem with propagation through singleton domains? (Don't use domain reduction before solving it.)
ANSWER_4 = None
Forward checking
Forward checking is even more restrictive than propagation through singletons: it never adds variables to the queue. (Later in this labs, we will perform tests to see which propagation algorithm performs best in terms of tradeoffs between performance and comprehensiveness.)
Instead of patterning our forward checking algorithm off of
domain_reduction
again, we'll write a fully general algorithm called
propagate
that encapsulates all three propagation strategies we've
seen: propagation through reduced domains, propagation through
singletons, and forward checking.
The function propagate
will be similar to the propagation algorithms
you've already defined. The difference is that it will take an
argument enqueue_condition_fn
which is the test that variables must
pass in order to be added to the queue: before propagate
adds a
variable to the queue, it should call enqueue_condition_fn(csp, var)
. If the function returns True
, it should add the variable to the
queue. Otherwise, it shouldn't.
def propagate(enqueue_condition_fn, csp, queue = None) : raise NotImplementedError
To review, the three enqueueing conditions we've seen are:
- domain reduction</dt>
- always add the variable to the queue </dd>
- singleton propagation</dt>
- add the variable if its domain has exactly one value in it. </dd>
- forward checking</dt>
- never add the variable to the queue. </dd>
Write functions for each of these tests. Hint: some of these functions may ignore some of their arguments.
def condition_domain_reduction(csp, var) : def condition_singleton(csp, var) : def condition_forward_checking(csp, var) :
And thus we can define:
domain_reduction_forward_checking = lambda csp, queue=None: propagate(condition_forward_checking, csp, queue)
A generic CSP solver
Write an algorithm that can solve a problem using any enqueueing
strategy. As a special case, if the enqueue_condition is None
, don't
use any propagation at all (i.e. the algorithm should perform only
depth-first search in this case.)
def solve_constraint_generic(problem, enqueue_condition=None) :
"""Solves the problem, calling propagate with the specified enqueue #todo formatting condition (a function). If enqueue_condition is None, uses DFS only. Same return type as solve_constraint_dfs."""
Answer the following question in your lab4.py file:
QUESTION 5: How many extensions does it take to solve the Pokemon problem #todo formatting with DFS and forward checking, but no propagation? (Don't use domain reduction before solving it.)
ANSWER_5 = None
Solving your own CSPs
Defining new constraints
Assuming m and n are integers, write a function that returns True if m and n are adjacent values (i.e. if they differ by exactly one) and False otherwise.
def constraint_adjacent(m, n) : raise NotImplementedError
Also write one for being non-adjacent. There are trivial ways to do
it; feel free to call constraint_adjacent
.
def constraint_not_adjacent(m, n) : raise NotImplementedError
The following example shows how you build a constraint object that requires two variables — call them A and B — to be different.
example_constraint = Constraint("A","B", constraint_different)
Some constraint problems include a constraint that requires all of
the variables to be different from one another. It can be tedious to
list all of the pairwise constraints by hand, so we won't. Write a
function that takes a list of variables and returns a list
containing, for each pair of variables, a constraint object
requiring them to be different from each other. (You can model the
constraints on the example above.) Note that order does NOT matter,
so you don't need to produce two different constraints for (A,B) and
(B,A).
specifically, do not duplicate constraints #todo incorporate above
def all_different(variables) : raise NotImplementedError
Defining a new problem: Moose problem (OPTIONAL)
If you want to try out your new constraints and CSP solver, you may design and solve a constraint satisfaction problem for the Moose Problem from 2008 Quiz 2. You are of course welcome to implement additional problems; some of our favorites include the Time Travelers problem (2009 Quiz 2) and the Zoo problem (2011 Quiz 2).
todo: insert description of moose problem, using people as variables and seats as values
Note: You will need to make a modified version of the constraint_adjacent function above to account for the table being round. (ie, seats 1 and 6 are adjacent, even though the numbers are far apart)
Interpret constraints that only mention one person (e.g. "McCain ...[todo]... seat 1") as an indication that you should leave out those values from the variable's domain; you won't need to make a Constraint to represent those kinds of constraints.
Establish the domains of the variables. Each variable will have a domain that's a subset of [1,2,3,4,5,6].
Establish the constraints. Remember the constraint that says that
all of the variables must be assigned a different value. You may
want to use csp.add_constraints(list)
.
To run local tests on your Moose Problem, set the boolean flag TEST_MOOSE_PROBLEM to True in lab4.py.
API Reference Documentation
In this lab, we provide an API for representing and manipulating partial solutions to constraint satisfaction problems.
Constraint Satisfaction Problems
A ConstraintSatisfactionProblem
is an object representing a
partially-solved constraint satisfaction problem. Its fields are:
- variables A list containing the names of all the variables in the problem.
- domains A dictionary associating each variable in the problem with its list of remaining values so far<a id="fnr.2" class="footref" href="#fn.2">2</a>.
- assigned_values A dictionary. Each variable which has already been
assigned a value is associated with that value
here. When the problem is entirely solved,
assigned_value
contains the solution. - unassigned_vars An ordered list of all the variables that still need to have a value assigned to them.
- constraints A list of the constraints between the variables in
the problem. Each constraint is a
Constraint
object;Constraint
objects are described in the next section.
Please note that while you may read any of the above variables, you
should probably not modify them directly; instead, you should use the
following API methods. (Below, csp
stands for some
ConstraintSatisfactionProblem
instance that you want to manipulate.)
- csp.get_domain(var) Return the list of values in the variable's domain.
- csp.set_domain(var, domain) Set the domain of the variable to the particular list of values.
- csp.eliminate(var, val) Remove the value from the variable's
domain. Note that as a helpful side-effect, this function returns
True
if the value was found in the domain, orFalse
if the value wasn't found.
- csp.get_assigned_value(var) If the variable has been assigned a
value, retrieve it. Returns
None
if the variable hasn't been assigned yet<a id="fnr.3" class="footref" href="#fn.3">3</a>. - csp.set_assigned_value(var, val) Set the assigned value of the variable to val, returning a modified copy of the constraint satisfaction problem. Throws an error if val is not in the domain of the variable, or if var has already been assigned a value.
- csp.constraints_between(var1, var2)
Return a list of all the
constraints between var1 and var2. Arguments that are
None
will match anything: for example,constraints_between('X',None)
will return all constraints involvingX
any any other variable, andconstraints_between(None, None)
will return all of the constraints in the problem. ! Please note that for your convenience, the constraints returned will always be altered to match the order of the arguments you passed to this method. For example,csp.constraints_between(None, 'Y')
will return a list of all constraints involving 'Y' — and the constraints will be altered so that 'Y' is their second variable (var2
) in every case. - csp.add_constraint(var1, var2, test_fn)
Takes two variables and a
function to act as a constraint between them, creating a
Constraint
object and adding it to the listcsp.constraints
. The functiontest_fn
must take two arguments — a value for the first variable, and a value for the second variable — and returnTrue
if the values satisfy the constraint, orFalse
otherwise. - csp.add_constraints(constraint_list)
Add a list of
Constraint
objects to the listcsp.constraints
. Useful for when you want to add several constraints to the problem at once, rather than one at a time usingcsp.add_constraint
.
Constraints
A Constraint
is a fairly basic object. It has three variables—
var1
, var2
, and constraint_fn
— and one method, check(val1,
val2)
.
const.check(val1, val2)
simply applies the Constraint
's
constraint function to the two arguments, returning True
if the
values satisfy the constraint, or False
otherwise.
</div>
</div>
Footnotes:
popped Alice off of the queue and are iterating over Alice's constraints. One of those constraints involves a neighbor, Bob. If Bob has a value that is incompatible with all of Alice's values,
remove Bob's value and add Bob to the queue.satisfaction involves ruling out as many values as
possible in order to limit search.a variable being assigned a value, and a variable having only one value left in its domain: a variable can have one value in its
domain without having an assigned value yet.Survey
Please answer these questions at the bottom of your lab3.py file:
- NAME: What is your name? (string)
- COLLABORATORS: Other than 6.034 staff, whom did you work with on this lab? (string, or empty string if you worked alone)
- HOW_MANY_HOURS_THIS_LAB_TOOK: Approximately how many hours did you spend on this lab? (number or string)
- WHAT_I_FOUND_INTERESTING: Which parts of this lab, if any, did you find interesting? (string)
- WHAT_I_FOUND_BORING: Which parts of this lab, if any, did you find boring or tedious? (string)
- (optional) SUGGESTIONS: What specific changes would you recommend, if any, to improve this lab for future years? (string)
(We'd ask which parts you find confusing, but if you're confused you should really ask a TA.)