Lab 3: Constraint Satisfaction
From 6.034 Wiki
(Difference between revisions)
Revision as of 22:53, 8 October 2015
1 Problems
1.1 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]
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.
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">constraint_equal</span>(a,b) :
<span style="color: #F0DFAF; font-weight: bold;">return</span> a == b
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">constraint_different</span>(a,b) :
<span style="color: #F0DFAF; font-weight: bold;">return</span> 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.
<span style="color: #DFAF8F;">pokemon_problem</span> = ConstraintSatisfactionProblem([<span style="color: #CC9393;">"Q1"</span>,<span style="color: #CC9393;">"Q2"</span>,<span style="color: #CC9393;">"Q3"</span>,<span style="color: #CC9393;">"Q4"</span>,<span style="color: #CC9393;">"Q5"</span>])
Here, we specify the values in each variable's domain.
pokemon_problem.set_domain(<span style="color: #CC9393;">"Q1"</span>,[<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>,<span style="color: #CC9393;">"C"</span>,<span style="color: #CC9393;">"D"</span>,<span style="color: #CC9393;">"E"</span>]) pokemon_problem.set_domain(<span style="color: #CC9393;">"Q2"</span>,[<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>,<span style="color: #CC9393;">"C"</span>,<span style="color: #CC9393;">"D"</span>,<span style="color: #CC9393;">"E"</span>]) pokemon_problem.set_domain(<span style="color: #CC9393;">"Q3"</span>,[<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>,<span style="color: #CC9393;">"C"</span>,<span style="color: #CC9393;">"D"</span>,<span style="color: #CC9393;">"E"</span>]) pokemon_problem.set_domain(<span style="color: #CC9393;">"Q4"</span>,[<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>,<span style="color: #CC9393;">"C"</span>,<span style="color: #CC9393;">"D"</span>,<span style="color: #CC9393;">"E"</span>]) pokemon_problem.set_domain(<span style="color: #CC9393;">"Q5"</span>,[<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>,<span style="color: #CC9393;">"C"</span>,<span style="color: #CC9393;">"D"</span>,<span style="color: #CC9393;">"E"</span>])
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(<span style="color: #CC9393;">"Q1"</span>,<span style="color: #CC9393;">"Q4"</span>, constraint_different) pokemon_problem.add_constraint(<span style="color: #CC9393;">"Q1"</span>,<span style="color: #CC9393;">"Q2"</span>, constraint_equal) pokemon_problem.add_constraint(<span style="color: #CC9393;">"Q3"</span>,<span style="color: #CC9393;">"Q2"</span>, constraint_different) pokemon_problem.add_constraint(<span style="color: #CC9393;">"Q3"</span>,<span style="color: #CC9393;">"Q4"</span>, constraint_different) pokemon_problem.add_constraint(<span style="color: #CC9393;">"Q4"</span>,<span style="color: #CC9393;">"Q5"</span>, 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:
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">(An alternative, which we won't use here.)</span> pokemon_problem.init_unassigned_vars([<span style="color: #CC9393;">"Q4"</span>,<span style="color: #CC9393;">"Q2"</span>,<span style="color: #CC9393;">"Q3"</span>,<span style="color: #CC9393;">"Q1"</span>,<span style="color: #CC9393;">"Q5"</span>])
(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.
1.2 Writing a depth-first search solver
Please write a constraint solver that uses depth-first search to find a solution.
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">solve_constraint_dfs</span>(csp) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
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).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).
NOTE: Once your function works, please modify it so that it returns not just
the solution, but a tuple (solution, extension_count) . The variable
extension_count should be a count of extensions made during search,
i.e. the number of times you removed an item from the agenda.
This is a helper function which you can use within
solve_constraint_dfs. It should return False if the problem's
assigned values violate some constraint, otherwise True.
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">check_all_assignments</span>(problem) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
1.3 Domain reduction
Domain reduction is a strategy for eliminating impossible values in advance to cut down on the amount of search you have to do.
First, you will need a utility function that can return all of the "neighbors" of a variable in a problem. The neighbors of a variable are the ones that share a constraint with it. Neighbors should appear AT MOST ONCE in the list; the list of neighbors should contain no duplicates.
Hint: csp.get_constraints may help.
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">get_neighbors</span>(csp, var) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
Next, you will need to write a domain-reduction algorithm.
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">domain_reduction</span>(csp, queue=<span style="color: #BFEBBF;">None</span>) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
Here is a rough description of the domain reduction algorithm:
- Establish a queue — if the optional argument
queuewas passed as an argument, use that as your queue. Otherwise,queueshould 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<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 a dictionary associating each variable with the list of values that domain reduction removed from its domain. (You don't need to include variables that had no values removed.)
Hint: You can remove values from a variable's domain using csp.eliminate(var, val).
1.3.1 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:
(a) How many extensions does it take to solve the pokemon problem if you don't use domain reduction before solving it?
(b) How many extensions does it take to solve the pokemon problem if you do use domain reduction before solving it?
1.4 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.
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">solve_constraint_propagate_reduced_domains</span>(problem) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
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's
neighbors 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.
1.5 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.
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">domain_reduction_singleton_domains</span>(csp, queue=<span style="color: #BFEBBF;">None</span>) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
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.
1.6 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.
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">propagate</span>(enqueue_condition_fn, csp, queue = <span style="color: #BFEBBF;">None</span>) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
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.
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">condition_domain_reduction</span>(csp, var) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">condition_singleton</span>(csp, var) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">condition_forward_checking</span>(csp, var) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
And thus we can define:
<span style="color: #DFAF8F;">domain_reduction_forward_checking</span> = <span style="color: #F0DFAF; font-weight: bold;">lambda</span> <span style="color: #DFAF8F;">csp</span>, <span style="color: #DFAF8F;">queue</span>=<span style="color: #BFEBBF;">None</span>: propagate(condition_forward_checking, csp, queue)
1.7 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.)
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">solve_constraint</span>(problem, enqueue_condition=<span style="color: #BFEBBF;">None</span>) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
1.8 Solving your own CSPs
1.8.1 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.
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">constraint_adjacent</span>(m, n) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
Also write one for being non-adjacent. There are simple ways to do
it; feel free to call constraint_adjacent.
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">constraint_not_adjacent</span>(m, n) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
The following example shows how you build a constraint object that requires two variables — call them A and B — to be different.
<span style="color: #DFAF8F;">example_constraint</span> = Constraint(<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>, 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).
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">all_different</span>(<span style="color: #93E0E3;">vars</span>) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
1.8.2 Defining a new problem
Design and solve a constraint satisfaction problem for the following word problem.
! You will need some new constraint functions.
Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?
Interpret constraints that only mention one person (e.g. "Baker does not live on the top floor.") 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.
<span style="color: #DFAF8F;">apartment_problem</span> = ConstraintSatisfactionProblem([<span style="color: #CC9393;">"Baker"</span>, <span style="color: #CC9393;">"Cooper"</span>, <span style="color: #CC9393;">"Fletcher"</span>, <span style="color: #CC9393;">"Miller"</span>, <span style="color: #CC9393;">"Smith"</span>])
Establish the domains of the variables. Each variable will have a domain that's a subset of [1,2,3,4,5].
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).
2 API Reference Documentation
In this lab, we provide an API for representing and manipulating partial solutions to constraint satisfaction problems.
2.1 Constraint Satisfaction Problems
A ConstraintSatisfactionProblem is an object representing a
partially-solved constraint satisfaction problem. Its fields are:
- variables</dt>
- A list containing the names of all the variables in the problem. </dd>
- domain</dt>
- 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>. </dd>
- assigned_value</dt>
- A dictionary. Each variable which has already been
assigned a value is associated with that value
here. When the problem is entirely solved,
assigned_valuecontains the solution. </dd> - unassigned_vars</dt>
- An ordered list of all the variables that still need to have a value assigned to them. </dd>
- constraints</dt>
- A list of the constraints between the variables in
the problem. Each constraint is a
Constraintobject;Constraintobjects are described in the next section. </dd>
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)</dt>
- Return the list of values in the variable's domain. </dd>
- csp.set_domain(var, domain)</dt>
- Set the domain of the variable to the particular list of values. </dd>
- csp.eliminate(var, val)</dt>
- Remove the value from the variable's
domain. As a bonus, returns
Trueif the value was found in the domain, orFalseif the value wasn't found. </dd>
- csp.get_assigned_value(var)</dt>
- If the variable has been assigned a
value, retrieve it. Returns
Noneif the variable hasn't been assigned yet<a id="fnr.3" class="footref" href="#fn.3">3</a>. </dd> - csp.set_assigned_value(var, val)</dt>
- Set the assigned value of the variable to val, returning the modified constraint satisfaction problem. As a side-effect, also automatically sets the domain of var to [val]. Throws an error if val is not in the domain of the variable, or if var has already been assigned a value. </dd>
- csp.constraints_between(var1, var2)</dt>
Returns a list of all the constraints between var1 and var2. Arguments that are
Nonewill match anything: for example,constraints_between('X',None)will return all constraints involvingXany 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.</dd>
- csp.add_constraint(var1, var2, test_fn)</dt>
Takes two variables and a function to act as a constraint between them, creating a
Constraintobject and adding it to the listcsp.constraints.The function
test_fnmust take two arguments — a value for the first variable, and a value for the second variable — and returnTrueif the values satisfy the constraint, orFalseotherwise.</dd>
- csp.add_constraints(constraint_list)</dt>
Adds a list of
Constraintobjects 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.</dd>
- csp.copy()</dt>
- Returns a (deep) copy of this constraint satisfaction
problem. This method is particularly useful because
you will want to make a copy of the
cspevery time you assign a value to a variable. </dd>
2.2 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.
3 Source
<span style="color: #F0DFAF; font-weight: bold;">class</span> <span style="color: #7CB8BB;">ConstraintSatisfactionProblem</span> :
<span style="color: #DFAF8F;">variables</span> = []
<span style="color: #DFAF8F;">constraints</span> = []
<span style="color: #DFAF8F;">unassigned_vars</span> = []
<span style="color: #DFAF8F;">domain</span> = {}
<span style="color: #DFAF8F;">assigned_value</span> = {}
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">__init__</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, variables, constraints=[]) :
<span style="color: #F0DFAF; font-weight: bold;">self</span>.variables = variables
<span style="color: #F0DFAF; font-weight: bold;">self</span>.constraints = constraints
<span style="color: #F0DFAF; font-weight: bold;">pass</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">set_domain</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var, domain) :
<span style="color: #F0DFAF; font-weight: bold;">if</span> var <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #F0DFAF; font-weight: bold;">in</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.variables :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">KeyError</span>(<span style="color: #93E0E3;">str</span>(var) + <span style="color: #CC9393;">" is not a variable in this problem."</span>)
<span style="color: #F0DFAF; font-weight: bold;">self</span>.domain[var] = <span style="color: #93E0E3;">set</span>(domain)
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">get_domain</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var) :
<span style="color: #F0DFAF; font-weight: bold;">if</span> var <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #F0DFAF; font-weight: bold;">in</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.variables :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">KeyError</span>(<span style="color: #93E0E3;">str</span>(var) + <span style="color: #CC9393;">" is not a variable in this problem."</span> + <span style="color: #93E0E3;">str</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>.variables))
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.domain.get(var, [])
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">eliminate</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var, val) :
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Removes the value from variable's domain. Returns True if</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">the domain contained the value when this function was</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">called; False if the domain didn't contain the value.</span>
<span style="color: #DFAF8F;">values</span> = <span style="color: #F0DFAF; font-weight: bold;">self</span>.domain.get(var, <span style="color: #93E0E3;">set</span>())
<span style="color: #DFAF8F;">found</span> = val <span style="color: #F0DFAF; font-weight: bold;">in</span> values
values.discard(val)
<span style="color: #F0DFAF; font-weight: bold;">self</span>.domain[var] = values
<span style="color: #F0DFAF; font-weight: bold;">return</span> found
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">get_assigned_value</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var) :
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.assigned_value.get(var, <span style="color: #BFEBBF;">None</span>)
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">set_assigned_value</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var, val) :
<span style="color: #F0DFAF; font-weight: bold;">if</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.assigned_value.get(var) <span style="color: #F0DFAF; font-weight: bold;">is</span> <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #BFEBBF;">None</span>:
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">AttributeError</span>(<span style="color: #CC9393;">"Can't assign variable "</span> + <span style="color: #93E0E3;">str</span>(var) + <span style="color: #CC9393;">" to value "</span> + <span style="color: #93E0E3;">str</span>(val) + <span style="color: #CC9393;">": var has already been assigned value "</span> + <span style="color: #93E0E3;">str</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>.assigned_value.get(var)) +<span style="color: #CC9393;">"."</span>)
<span style="color: #F0DFAF; font-weight: bold;">elif</span> val <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #F0DFAF; font-weight: bold;">in</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.get_domain(var) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">KeyError</span>(<span style="color: #CC9393;">"The domain of "</span> + <span style="color: #93E0E3;">str</span>(var) + <span style="color: #CC9393;">" does not contain the value "</span> + <span style="color: #93E0E3;">str</span>(val) + <span style="color: #CC9393;">"."</span>)
<span style="color: #F0DFAF; font-weight: bold;">else</span> :
<span style="color: #F0DFAF; font-weight: bold;">self</span>.assigned_value[var] = val
<span style="color: #F0DFAF; font-weight: bold;">self</span>.domain[var] = <span style="color: #93E0E3;">set</span>([val])
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>
<span style="color: #7F9F7F;">#</span><span style="color: #7F9F7F;">x = self.deepcopy()</span>
<span style="color: #7F9F7F;">#</span><span style="color: #7F9F7F;">x.assigned_value[var] = val</span>
<span style="color: #7F9F7F;">#</span><span style="color: #7F9F7F;">x.set_domain(var, set([val]))</span>
<span style="color: #7F9F7F;">#</span><span style="color: #7F9F7F;">return x</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">add_constraints</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, constraint_list) :
<span style="color: #F0DFAF; font-weight: bold;">self</span>.constrants += constraint_list
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">add_constraint</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var1, var2, constraint_fn) :
<span style="color: #F0DFAF; font-weight: bold;">self</span>.constraints.append(Constraint(var1, var2, constraint_fn))
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">constraints_between</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var1=<span style="color: #BFEBBF;">None</span>, var2=<span style="color: #BFEBBF;">None</span>) :
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Returns a list of constraints in the problem. If either</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">variable is provided, returns only variables that start/end</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">at those variables.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! The returned constraints will be transformed so that var1</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! comes first and var2 comes second, as requested.</span>
<span style="color: #DFAF8F;">pred1</span> = <span style="color: #F0DFAF; font-weight: bold;">lambda</span> node : (var1 <span style="color: #F0DFAF; font-weight: bold;">is</span> <span style="color: #BFEBBF;">None</span>) <span style="color: #F0DFAF; font-weight: bold;">or</span> (node == var1)
<span style="color: #DFAF8F;">pred2</span> = <span style="color: #F0DFAF; font-weight: bold;">lambda</span> node : (var2 <span style="color: #F0DFAF; font-weight: bold;">is</span> <span style="color: #BFEBBF;">None</span>) <span style="color: #F0DFAF; font-weight: bold;">or</span> (node == var2)
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #93E0E3;">filter</span>(
<span style="color: #F0DFAF; font-weight: bold;">lambda</span> e : e <span style="color: #F0DFAF; font-weight: bold;">is</span> <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #BFEBBF;">None</span>,
[e <span style="color: #F0DFAF; font-weight: bold;">if</span> pred1(e.var1) <span style="color: #F0DFAF; font-weight: bold;">and</span> pred2(e.var2) <span style="color: #F0DFAF; font-weight: bold;">else</span>
e.reverse() <span style="color: #F0DFAF; font-weight: bold;">if</span> pred2(e.var1) <span style="color: #F0DFAF; font-weight: bold;">and</span> pred1(e.var2)
<span style="color: #F0DFAF; font-weight: bold;">else</span> <span style="color: #BFEBBF;">None</span>
<span style="color: #F0DFAF; font-weight: bold;">for</span> e <span style="color: #F0DFAF; font-weight: bold;">in</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.constraints
])
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">init_unassigned_vars</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, unassigned_vars=<span style="color: #BFEBBF;">None</span>) :
<span style="color: #F0DFAF; font-weight: bold;">if</span> unassigned_vars <span style="color: #F0DFAF; font-weight: bold;">is</span> <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #BFEBBF;">None</span> <span style="color: #F0DFAF; font-weight: bold;">and</span> <span style="color: #F0DFAF; font-weight: bold;">not</span> (<span style="color: #93E0E3;">set</span>(unassigned_vars) <= <span style="color: #93E0E3;">set</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>.variables)) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">AttributeError</span>(<span style="color: #CC9393;">"Unassigned_Vars contains items that are not variables in this problem."</span>)
<span style="color: #F0DFAF; font-weight: bold;">self</span>.unassigned_vars = (unassigned_vars <span style="color: #F0DFAF; font-weight: bold;">or</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.variables) + []
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">copy</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>) :
<span style="color: #DFAF8F;">x</span> = deepcopy(<span style="color: #F0DFAF; font-weight: bold;">self</span>)
<span style="color: #DFAF8F;">x.unassigned_vars</span> = x.unassigned_vars + []
<span style="color: #DFAF8F;">x.assigned_value</span> = deepcopy(x.assigned_value)
<span style="color: #F0DFAF; font-weight: bold;">return</span> x
<span style="color: #F0DFAF; font-weight: bold;">from</span> copy <span style="color: #F0DFAF; font-weight: bold;">import</span> deepcopy
<span style="color: #F0DFAF; font-weight: bold;">class</span> <span style="color: #7CB8BB;">Constraint</span> :
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">__init__</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var1, var2, constraint_fn) :
<span style="color: #F0DFAF; font-weight: bold;">self</span>.var1 = var1
<span style="color: #F0DFAF; font-weight: bold;">self</span>.var2 = var2
<span style="color: #F0DFAF; font-weight: bold;">self</span>.constraint_fn = constraint_fn
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">reverse</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>) :
<span style="color: #F0DFAF; font-weight: bold;">return</span> Constraint(<span style="color: #F0DFAF; font-weight: bold;">self</span>.var2, <span style="color: #F0DFAF; font-weight: bold;">self</span>.var1, <span style="color: #F0DFAF; font-weight: bold;">lambda</span> a,b: <span style="color: #F0DFAF; font-weight: bold;">self</span>.constraint_fn(b,a))
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">check</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, val1, val2) :
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.constraint_fn(val1, val2)
<span style="color: #F0DFAF; font-weight: bold;">from</span> copy <span style="color: #F0DFAF; font-weight: bold;">import</span> deepcopy
<span style="color: #F0DFAF; font-weight: bold;">class</span> <span style="color: #7CB8BB;">Constraint</span> :
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">__init__</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var1, var2, constraint_fn) :
<span style="color: #F0DFAF; font-weight: bold;">self</span>.var1 = var1
<span style="color: #F0DFAF; font-weight: bold;">self</span>.var2 = var2
<span style="color: #F0DFAF; font-weight: bold;">self</span>.constraint_fn = constraint_fn
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">reverse</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>) :
<span style="color: #F0DFAF; font-weight: bold;">return</span> Constraint(<span style="color: #F0DFAF; font-weight: bold;">self</span>.var2, <span style="color: #F0DFAF; font-weight: bold;">self</span>.var1, <span style="color: #F0DFAF; font-weight: bold;">lambda</span> a,b: <span style="color: #F0DFAF; font-weight: bold;">self</span>.constraint_fn(b,a))
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">check</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, val1, val2) :
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.constraint_fn(val1, val2)
<span style="color: #F0DFAF; font-weight: bold;">class</span> <span style="color: #7CB8BB;">ConstraintSatisfactionProblem</span> :
<span style="color: #DFAF8F;">variables</span> = []
<span style="color: #DFAF8F;">constraints</span> = []
<span style="color: #DFAF8F;">unassigned_vars</span> = []
<span style="color: #DFAF8F;">domain</span> = {}
<span style="color: #DFAF8F;">assigned_value</span> = {}
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">__init__</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, variables, constraints=[]) :
<span style="color: #F0DFAF; font-weight: bold;">self</span>.variables = variables
<span style="color: #F0DFAF; font-weight: bold;">self</span>.constraints = constraints
<span style="color: #F0DFAF; font-weight: bold;">pass</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">set_domain</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var, domain) :
<span style="color: #F0DFAF; font-weight: bold;">if</span> var <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #F0DFAF; font-weight: bold;">in</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.variables :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">KeyError</span>(<span style="color: #93E0E3;">str</span>(var) + <span style="color: #CC9393;">" is not a variable in this problem."</span>)
<span style="color: #F0DFAF; font-weight: bold;">self</span>.domain[var] = <span style="color: #93E0E3;">set</span>(domain)
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">get_domain</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var) :
<span style="color: #F0DFAF; font-weight: bold;">if</span> var <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #F0DFAF; font-weight: bold;">in</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.variables :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">KeyError</span>(<span style="color: #93E0E3;">str</span>(var) + <span style="color: #CC9393;">" is not a variable in this problem."</span> + <span style="color: #93E0E3;">str</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>.variables))
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.domain.get(var, [])
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">eliminate</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var, val) :
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Removes the value from variable's domain. Returns True if</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">the domain contained the value when this function was</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">called; False if the domain didn't contain the value.</span>
<span style="color: #DFAF8F;">values</span> = <span style="color: #F0DFAF; font-weight: bold;">self</span>.domain.get(var, <span style="color: #93E0E3;">set</span>())
<span style="color: #DFAF8F;">found</span> = val <span style="color: #F0DFAF; font-weight: bold;">in</span> values
values.discard(val)
<span style="color: #F0DFAF; font-weight: bold;">self</span>.domain[var] = values
<span style="color: #F0DFAF; font-weight: bold;">return</span> found
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">get_assigned_value</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var) :
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.assigned_value.get(var, <span style="color: #BFEBBF;">None</span>)
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">set_assigned_value</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var, val) :
<span style="color: #F0DFAF; font-weight: bold;">if</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.assigned_value.get(var) <span style="color: #F0DFAF; font-weight: bold;">is</span> <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #BFEBBF;">None</span>:
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">AttributeError</span>(<span style="color: #CC9393;">"Can't assign variable "</span> + <span style="color: #93E0E3;">str</span>(var) + <span style="color: #CC9393;">" to value "</span> + <span style="color: #93E0E3;">str</span>(val) + <span style="color: #CC9393;">": var has already been assigned value "</span> + <span style="color: #93E0E3;">str</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>.assigned_value.get(var)) +<span style="color: #CC9393;">"."</span>)
<span style="color: #F0DFAF; font-weight: bold;">elif</span> val <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #F0DFAF; font-weight: bold;">in</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.get_domain(var) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">KeyError</span>(<span style="color: #CC9393;">"The domain of "</span> + <span style="color: #93E0E3;">str</span>(var) + <span style="color: #CC9393;">" does not contain the value "</span> + <span style="color: #93E0E3;">str</span>(val) + <span style="color: #CC9393;">"."</span>)
<span style="color: #F0DFAF; font-weight: bold;">else</span> :
<span style="color: #F0DFAF; font-weight: bold;">self</span>.assigned_value[var] = val
<span style="color: #F0DFAF; font-weight: bold;">self</span>.domain[var] = <span style="color: #93E0E3;">set</span>([val])
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>
<span style="color: #7F9F7F;">#</span><span style="color: #7F9F7F;">x = self.deepcopy()</span>
<span style="color: #7F9F7F;">#</span><span style="color: #7F9F7F;">x.assigned_value[var] = val</span>
<span style="color: #7F9F7F;">#</span><span style="color: #7F9F7F;">x.set_domain(var, set([val]))</span>
<span style="color: #7F9F7F;">#</span><span style="color: #7F9F7F;">return x</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">add_constraints</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, constraint_list) :
<span style="color: #F0DFAF; font-weight: bold;">self</span>.constrants += constraint_list
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">add_constraint</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var1, var2, constraint_fn) :
<span style="color: #F0DFAF; font-weight: bold;">self</span>.constraints.append(Constraint(var1, var2, constraint_fn))
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">constraints_between</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, var1=<span style="color: #BFEBBF;">None</span>, var2=<span style="color: #BFEBBF;">None</span>) :
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Returns a list of constraints in the problem. If either</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">variable is provided, returns only variables that start/end</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">at those variables.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! The returned constraints will be transformed so that var1</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! comes first and var2 comes second, as requested.</span>
<span style="color: #DFAF8F;">pred1</span> = <span style="color: #F0DFAF; font-weight: bold;">lambda</span> node : (var1 <span style="color: #F0DFAF; font-weight: bold;">is</span> <span style="color: #BFEBBF;">None</span>) <span style="color: #F0DFAF; font-weight: bold;">or</span> (node == var1)
<span style="color: #DFAF8F;">pred2</span> = <span style="color: #F0DFAF; font-weight: bold;">lambda</span> node : (var2 <span style="color: #F0DFAF; font-weight: bold;">is</span> <span style="color: #BFEBBF;">None</span>) <span style="color: #F0DFAF; font-weight: bold;">or</span> (node == var2)
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #93E0E3;">filter</span>(
<span style="color: #F0DFAF; font-weight: bold;">lambda</span> e : e <span style="color: #F0DFAF; font-weight: bold;">is</span> <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #BFEBBF;">None</span>,
[e <span style="color: #F0DFAF; font-weight: bold;">if</span> pred1(e.var1) <span style="color: #F0DFAF; font-weight: bold;">and</span> pred2(e.var2) <span style="color: #F0DFAF; font-weight: bold;">else</span>
e.reverse() <span style="color: #F0DFAF; font-weight: bold;">if</span> pred2(e.var1) <span style="color: #F0DFAF; font-weight: bold;">and</span> pred1(e.var2)
<span style="color: #F0DFAF; font-weight: bold;">else</span> <span style="color: #BFEBBF;">None</span>
<span style="color: #F0DFAF; font-weight: bold;">for</span> e <span style="color: #F0DFAF; font-weight: bold;">in</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.constraints
])
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">init_unassigned_vars</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>, unassigned_vars=<span style="color: #BFEBBF;">None</span>) :
<span style="color: #F0DFAF; font-weight: bold;">if</span> unassigned_vars <span style="color: #F0DFAF; font-weight: bold;">is</span> <span style="color: #F0DFAF; font-weight: bold;">not</span> <span style="color: #BFEBBF;">None</span> <span style="color: #F0DFAF; font-weight: bold;">and</span> <span style="color: #F0DFAF; font-weight: bold;">not</span> (<span style="color: #93E0E3;">set</span>(unassigned_vars) <= <span style="color: #93E0E3;">set</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>.variables)) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">AttributeError</span>(<span style="color: #CC9393;">"Unassigned_Vars contains items that are not variables in this problem."</span>)
<span style="color: #F0DFAF; font-weight: bold;">self</span>.unassigned_vars = (unassigned_vars <span style="color: #F0DFAF; font-weight: bold;">or</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>.variables) + []
<span style="color: #F0DFAF; font-weight: bold;">return</span> <span style="color: #F0DFAF; font-weight: bold;">self</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">copy</span>(<span style="color: #F0DFAF; font-weight: bold;">self</span>) :
<span style="color: #DFAF8F;">x</span> = deepcopy(<span style="color: #F0DFAF; font-weight: bold;">self</span>)
<span style="color: #DFAF8F;">x.unassigned_vars</span> = x.unassigned_vars + []
<span style="color: #DFAF8F;">x.assigned_value</span> = deepcopy(x.assigned_value)
<span style="color: #F0DFAF; font-weight: bold;">return</span> x
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">--------------- FOR STUDENTS</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Q0. Understand the following terms: variable, domain, value, constraint.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">THE FOLLOWING IS A CONSTRAINT SATISFACTION PROBLEM:</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">[insert the Pokemon problem here]</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">This part of the lab will help you become familiar with our</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">constraint satisfaction API.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">This problem requires two kinds of constraint: a must-be-equal</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">constraint and a must-not-be-equal constraint. In this lab,</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">constraints are defined using functions that take the values of two</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">variables as arguments and return True or False based on whether the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">constraint is satisfied or not.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Here are definitions for the must-be-equal and must-not-be-equal</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">constraints.</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">constraint_equal</span>(a,b) :
<span style="color: #F0DFAF; font-weight: bold;">return</span> a == b
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">constraint_different</span>(a,b) :
<span style="color: #F0DFAF; font-weight: bold;">return</span> a != b
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">To set up the problem, we first establish a new</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">ConstraintSatisfactionProblem instance. There are five variables ---</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">the five questions to be answered.</span>
<span style="color: #DFAF8F;">pokemon_problem</span> = ConstraintSatisfactionProblem([<span style="color: #CC9393;">"Q1"</span>,<span style="color: #CC9393;">"Q2"</span>,<span style="color: #CC9393;">"Q3"</span>,<span style="color: #CC9393;">"Q4"</span>,<span style="color: #CC9393;">"Q5"</span>])
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Here, we specify which values are in each variable's domain.</span>
pokemon_problem.set_domain(<span style="color: #CC9393;">"Q1"</span>,[<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>,<span style="color: #CC9393;">"C"</span>,<span style="color: #CC9393;">"D"</span>,<span style="color: #CC9393;">"E"</span>])
pokemon_problem.set_domain(<span style="color: #CC9393;">"Q2"</span>,[<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>,<span style="color: #CC9393;">"C"</span>,<span style="color: #CC9393;">"D"</span>,<span style="color: #CC9393;">"E"</span>])
pokemon_problem.set_domain(<span style="color: #CC9393;">"Q3"</span>,[<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>,<span style="color: #CC9393;">"C"</span>,<span style="color: #CC9393;">"D"</span>,<span style="color: #CC9393;">"E"</span>])
pokemon_problem.set_domain(<span style="color: #CC9393;">"Q4"</span>,[<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>,<span style="color: #CC9393;">"C"</span>,<span style="color: #CC9393;">"D"</span>,<span style="color: #CC9393;">"E"</span>])
pokemon_problem.set_domain(<span style="color: #CC9393;">"Q5"</span>,[<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>,<span style="color: #CC9393;">"C"</span>,<span style="color: #CC9393;">"D"</span>,<span style="color: #CC9393;">"E"</span>])
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Here, we set up constraints. Each constraint takes two variable</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">names, and a binary predicate.</span>
pokemon_problem.add_constraint(<span style="color: #CC9393;">"Q1"</span>,<span style="color: #CC9393;">"Q4"</span>, constraint_different)
pokemon_problem.add_constraint(<span style="color: #CC9393;">"Q1"</span>,<span style="color: #CC9393;">"Q2"</span>, constraint_equal)
pokemon_problem.add_constraint(<span style="color: #CC9393;">"Q3"</span>,<span style="color: #CC9393;">"Q2"</span>, constraint_different)
pokemon_problem.add_constraint(<span style="color: #CC9393;">"Q3"</span>,<span style="color: #CC9393;">"Q4"</span>, constraint_different)
pokemon_problem.add_constraint(<span style="color: #CC9393;">"Q4"</span>,<span style="color: #CC9393;">"Q5"</span>, constraint_equal)
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Finally, init_unassigned_vars tells the problem which variables need</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">to be assigned, and in what order. If passed no argument, it simply</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">includes all of the variables in the problem in some arbitrary</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">order.</span>
pokemon_problem.init_unassigned_vars()
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">You can also pass an argument to specify the order of the unassigned_vars yourself:</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">(Some problems can be solved more efficiently by choosing a good</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">ordering of the variables.)</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">pokemon_problem.init_unassigned_vars(["Q4","Q2","Q3","Q1","Q5"])</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">This problem is now ready to be solved --- all we need is a CSP</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">solver.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">PROBLEM ONE: WRITE A DEPTH-FIRST SEARCH CONSTRAINT SOLVER</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Please write a constraint solver that uses DEPTH-FIRST SEARCH to</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">find a solution.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Hint: This is exactly depth-first search as in the search lab, but</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">this time the items in the agenda are partially-solved problems, not</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">paths.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Create an agenda containing the problem. Until the agenda is empty,</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">pop the first problem off the list. Check whether the problem has</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">any unassigned variables (csp.unassigned_vars). If there are no</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">unassigned vars, make sure that all of the assignments satisfy all</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">of the constraints (csp.constraints is the problem's list of</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">constraints. A constraint has fields var1, var2, and a method</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">check(val1, val2) which returns True if the constraint is satisfied,</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">and False otherwise).</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">If a problem has no unassigned variables and it satisfies all of the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">constraints, you've succeeded! Return the list of</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">assignments. (csp.assigned_value). If it violates some of the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">constraints, skip it and continue.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">If the problem has some unassigned variables, take the first</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">unassigned variable off the list (csp.unassigned_vars). For each</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">value in the variable's domain (csp.get_domain(var)), create a new</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">copy of the csp. (csp_new = csp.copy()). Using the copy, assign the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">value to the variable. (csp_new.set_assigned_value(var, val)</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">). Collect all of the copies and add them to the front of the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">agenda.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">This is a helper function. It should return False if the problem's</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">assigned values violate some constraint, otherwise True. </span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">check_all_constraints</span>(problem) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">solve_constraint_dfs</span>(problem) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! Once your function works, please modify it so that it returns not</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! just the solution, but a tuple (solution, extension_count). The</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! variable extension_count should be a count of extensions made</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! during search, i.e. the number of times you removed an item from</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! the agenda.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">QUESTION TWO: DOMAIN REDUCTION</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Domain reduction is a strategy for eliminating impossible values in</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">advance to cut down on the amount of search you have to do.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">First, you will need a utility function that can return all of the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">"neighbors" of a variable in a problem. The neighbors of a variable</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">are the ones that share a constraint with it. Neighbors should</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">appear AT MOST ONCE in the list; the list of neighbors should</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">contain no duplicates.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Hint: csp.get_constraints may help. </span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">get_neighbors</span>(csp, var) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Next, you will need to write a domain-reduction algorithm.</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">domain_reduction</span>(csp, queue=<span style="color: #BFEBBF;">None</span>) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Establish a queue. If queue was passed as an argument, use it as</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">your queue. Otherwise, queue should contain all the variables in the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">problem. Until the queue is empty, pop the first variable off the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">queue. Iterate over the variable's constraints: if a neighbor has a</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">value that violates a constraint with EVERY value in the variable's</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">domain, remove the neighbor's value and add the neighbor to the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">queue.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">If any variable has an empty domain, quit immediately and return None.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">If the queue is empty, domain reduction has finished; please return</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">a list of the variables that your algorithm added to the queue. Each</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">variables should appear at most once, and order does not matter.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Hint: You can remove values using csp.eliminate(var, val).</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">~ta note: important to ignore assigned variables?</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Q. You can solve the pokemon problem by calling</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">solve_constraint_dfs(pokemon_problem). It could be faster, however,</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">to run domain reduction on it before attempting to solve it ---</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">(a) How many extensions does it take to solve the pokemon problem if</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">you DON'T use domain reduction before solving it?</span>
<span style="color: #DFAF8F;">ANSWER_1</span> = <span style="color: #BFEBBF;">None</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">(b) How many extensions does it take to solve the pokemon problem if</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">you DO use domain reduction before solving it?</span>
<span style="color: #DFAF8F;">ANSWER_2</span> = <span style="color: #BFEBBF;">None</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">QUESTION THREE: PROPAGATION THROUGH REDUCED DOMAINS</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Domain reduction can be used not only before search, but also during</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">search. When used during search, domain reduction can make use of</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">the assignments you've made to further reduce the search space. The</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">result is a new csp solution method: propagation through reduced</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">domains.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">You can reuse most of your code from your solve_constraint_dfs</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">algorithm, as domain reduction adds only a single conditional</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">statement: every time you assign a value to a variable, you must</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">call your domain_reduction function with the neighbors of the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">variable as an argument. If the domain_reduction function returns</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">None, the problem can't be solved with the given assignments ---</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">don't add the problem to the agenda. Otherwise, add the problem to</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">the agenda as usual.</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">solve_constraint_propagate_reduced_domains</span>(problem) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">QUESTION FOUR: PROPAGATION THROUGH SINGLETON DOMAINS</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Propagation through singleton domains is an alternative which is</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">less expensive than propagating through reduced domains, because it</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">performs fewer checks.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Propagation through singletons is exactly like propagation through</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">reduced domains, except that variables must pass a test in order for</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">your algorithm to add them to the queue: only add variables to the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">queue if they have exactly one value in their domain.</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">domain_reduction_singleton_domains</span>(problem, queue=<span style="color: #BFEBBF;">None</span>) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">solve_constraint_propagate_singleton_domains</span>(problem) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #7F9F7F;">#</span><span style="color: #7F9F7F;">~ta note: the difference between propagating all variables of size</span>
<span style="color: #7F9F7F;">#</span><span style="color: #7F9F7F;">one, all reduced variables of size one, etc.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">QUESTION FIVE: FORWARD CHECKING</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Forward checking is even more restrictive: it /never/ adds variables</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">to the queue.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Instead of modifying domain_reduction to make our forward_checking</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">algorithm, we'll write a fully general algorithm that encapsulates</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">propagation through reduced domains, propagation through singletons,</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">and forward checking.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">The function propagate will perform the generic domain reduction. It</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">takes an argument enqueue_condition_fn which is a test that</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">variables must pass in order to be added to the queue. Before</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">propagate adds a variable to the queue, it calls</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">enqueue_condition_fn(problem, var). If the function returns True, it</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">adds the variable to the queue. Otherwise, it doesn't.</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">propagate</span>(enqueue_condition_fn, problem, queue = <span style="color: #BFEBBF;">None</span>) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">The three enqueueing conditions we've seen are:</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">- domain reduction: always add the variable to the queue</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">- singleton propagation: add the variable if its domain is size 1.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">- forward checking: never add the variable to the queue.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Write functions for each of these tests. Hint: some of these</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">functions may ignore some of their arguments.</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">condition_domain_reduction</span>(problem, var) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">condition_singleton</span>(problem, var) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">condition_forward_checking</span>(problem, var) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">QUESTION SIX: GENERIC CSP SOLVER</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Write an algorithm that can solve a problem using any enqueueing</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">strategy. As a special case, if the enqueue_condition is None, don't</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">use any propagation at all (i.e. the algorithm should perform</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">depth-first search only in this case.)</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">solve_constraint</span>(problem, enqueue_condition=<span style="color: #BFEBBF;">None</span>) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">QUESTION SEVEN: DEFINING CUSTOM CONSTRAINTS</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Assuming m and n are integers, write a function that returns True if</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">m and n are adjacent values (i.e. if they differ by exactly one) and</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">False otherwise.</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">constraint_adjacent</span>(m, n) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Also write one for being non-adjacent. There are simple ways to do</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">it; feel free to call constraint_adjacent.</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">constraint_not_adjacent</span>(m, n) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">The following example shows how you build a constraint object that</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">requires two variables --- call them A and B --- to be different.</span>
<span style="color: #DFAF8F;">example_constraint</span> = Constraint(<span style="color: #CC9393;">"A"</span>,<span style="color: #CC9393;">"B"</span>, constraint_different)
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Some constraint problems include a constraint that requires all of</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">the variables to be different from one another. It can be tedious to</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">list all of the pairwise constraints by hand, so we won't. Write a</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">function that takes a list of variables and returns a list</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">containing, for each pair of variables, a constraint object</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">requiring them to be different from each other. (You can model the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">constraints on the example above.) Note that order does NOT matter,</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">so you don't need to produce two different constraints for (A,B) and</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">(B,A).</span>
<span style="color: #F0DFAF; font-weight: bold;">def</span> <span style="color: #8CD0D3;">all_different</span>(<span style="color: #93E0E3;">vars</span>) :
<span style="color: #F0DFAF; font-weight: bold;">raise</span> <span style="color: #7CB8BB;">NotImplementedError</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">QUESTION EIGHT: FUN WITH PROBLEM-SOLVING</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Design and solve a constraint satisfaction problem for the following</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">word problem.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! You will need some new constraint functions.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Baker, Cooper, Fletcher, Miller, and Smith live on different floors</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">of an apartment house that contains only five floors. Baker does not</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">live on the top floor. Cooper does not live on the bottom</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">floor. Fletcher does not live on either the top or the bottom</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">floor. Miller lives on a higher floor than does Cooper. Smith does</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">not live on a floor adjacent to Fletcher's. Fletcher does not live</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">on a floor adjacent to Cooper's. Where does everyone live?</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! Interpret constraints that only mention one person (e.g. "Baker</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! does not live on the top floor.") as an indication that you should</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! leave out those values from the variable's domain --- you won't</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">! need to make a constraint to represent those kinds of constraints.</span>
<span style="color: #DFAF8F;">apartment_problem</span> = ConstraintSatisfactionProblem([<span style="color: #CC9393;">"Baker"</span>, <span style="color: #CC9393;">"Cooper"</span>, <span style="color: #CC9393;">"Fletcher"</span>, <span style="color: #CC9393;">"Miller"</span>, <span style="color: #CC9393;">"Smith"</span>])
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Establish the domains of the variables. Each variable will have a</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">domain that's a subset of [1,2,3,4,5].</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Establish the constraints. Remember the constraint that says that</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">all of the variables must be assigned a different value. You may</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">want to use csp.add_constraints(list).</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">QUESTION NINE: QUIZ PRACTICE</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">For practice on the quizzes, see if your constraint solver gets the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">same solutions as you do on the 6.034 quizzes. Our favorite csp quiz</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">problems include:</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">- the time traveler problem</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">- the zoo problem</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">- the pokemon problem</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">For additional fun, see if you can include print statements in your</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">generic constraint solver so that your algorithm will walk you</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">through the process of solving a quiz problem: how to draw the</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">search tree, which values to cross off, and when to backtrack.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">QUESTION TEN: BENCHMARKS</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">How should you order your variables in the agenda? e.g.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">- most constrained variables first</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">- smallest domains first</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Let's find out empirically.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">QUESTION ELEVEN: RESOURCE ALLOCATION</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Find out how many values you need using binary search.</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">QUESTION TWELVE: COUNTING SOLUTIONS</span>
<span style="color: #7F9F7F;"># </span><span style="color: #7F9F7F;">Use "yield" to count the number of solutions.</span>
Footnotes:
<a id="fn.1" class="footnum" href="#fnr.1">1</a>
Naming the variables may make this easier: you have
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.<a id="fn.2" class="footnum" href="#fnr.2">2</a>
Constraint
satisfaction involves ruling out as many values as
possible in order to limit search.<a id="fn.3" class="footnum" href="#fnr.3">3</a>
Please note that there is a distinction between
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.
