From 6.034 Wiki
This lab is due by Tuesday, October 27 at 10:00pm.
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 and change log 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/.
Note: If you downloaded the lab files on or before October 15, you will need to download a new version of tester.py in order to transmit ConstraintSatisfactionProblem objects to the server and pass the online tests.
Your answers for this lab belong in the main file lab4.py.
Setting up a Constraint Satisfaction Problem
Before beginning, you may want to familiarize yourself with the following terms: variable, value, domain, constraint, assignment.
The Pokemon problem from 2012 Quiz 2, pages 2-4, is an example of a problem that can be solved using constrained search:
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: API.
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)
By default, the unassigned_vars list is initialized in alphabetical order.
To specify the order yourself, you can call .set_unassigned_vars_order with an ordered list of the unassigned variables:
# (An alternative, which we won't use here.) pokemon_problem.set_unassigned_vars_order(["Q4","Q2","Q3","Q1","Q5"])
(For some problems, efficiently re-ordering the variables can make a large difference in performance.)
We have set up the variables, the domains, and the constraints.
The Pokemon problem is defined for you in test_problems.py. To get a copy of it, use the method get_pokemon_problem() in lab4.py.
This problem is now ready to be solved — all we need is a CSP solver.
Writing a depth-first search solver
Your first task is to write a constraint solver that uses depth-first search to
find a solution. Start by writing these two helper functions, which may be useful within
def has_empty_domains(csp) : "Returns True if csp has one or more empty domains, otherwise False"
def check_all_constraints(csp) : """Return False if the problem's assigned values violate some constraint, otherwise True"""
Each function takes in an argument csp, which is a ConstraintSatisfactionProblem instance.
Now you can use the helper functions to write the constraint solver:
def solve_constraint_dfs(problem) :
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. Initialize the extension count to 0.
- Until the agenda is empty, pop the first problem off the list and increment the extension count by 1.
- Immediately check if the domain of any of the variables is empty. If any domain is empty, the problem is unsolvable with the current assignments; continue with the next iteration of the loop. Otherwise, begin solving the problem.
- 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_values). The return type should be a tuple
(solution, extension_count), containing:
- the solution (
csp.assigned_values, which is a dictionary mapping variables to assigned values), and
- the number of extensions made (the number of problems popped off the agenda).
- the solution (
If the problem has some unassigned variables:
- Take the first unassigned variable off the list (csp.pop_next_unassigned_var()).
- 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. (
- Collect the list of copies and add the list to the front of the agenda (as is appropriate for depth-first search). For consistency, keep the list of copies in the same order that the copies were created (the same as the order of values in the variable's domain).
- If the loop has exited because the agenda is empty, the problem is completely unsolvable. Return a tuple comprised of None (instead of a solution) and the number of extensions.
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. This function should return an alphabetically sorted list of the neighbors whose domains were reduced, with each neighbor appearing AT MOST ONCE in the list (the list should contain no duplicates). If no domains are reduced, return an empty list; if a domain is reduced to size 0 (no values left in domain), quit and immediately return None. This method should modify the input csp.
Hint: csp.constraints_between may help.
def eliminate_from_neighbors(csp, var) :
Next, you will need to write a domain-reduction algorithm.
def domain_reduction(csp, queue=None) :
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 in their default order. (Hint: csp.get_all_variables() will make a copy of the variables list.)
- 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 first variable's domain, remove the neighbor's value and add the neighbor to the queue, unless the neighbor is already in the queue. Add neighbors to the queue in alphabetical order (this will probably be the same as the default order).
- If any variable has an empty domain, quit immediately and return None.
- When the queue is empty, domain reduction has finished. As a side-effect, please return a list of all variables that were dequeued, in the order they were removed from the queue. Variables may appear in this list multiple times.
This method should modify the input csp.
Hint: You can remove values from a variable's domain using
(But don't eliminate values from a variable while iterating over its domain, or Python will get confused.)
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 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
domain_reduction function with a list containing just the assigned variable as an argument. (This will look for and eliminate incompatible values from variables' domains.) Then add the problem to the agenda as usual.
domain_reduction eliminates all values from a variable's domain, the problem will be recognized as unsolvable when it is next popped off the agenda.)
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
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.
Now, you can use domain_reduction_singleton_domains to write a constraint solver that propagates through singleton domains:
def solve_constraint_propagate_singleton_domains(problem) :
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 is even more restrictive than propagation through singletons: it never adds variables to the queue.
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.
propagate will be similar to the propagation algorithms
you've already defined. The difference is that it will take an
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
. 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
- always add the variable to the queue
- singleton propagation
- add the variable if its domain has exactly one value in it.
- forward checking
- never add the variable to the queue.
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) :
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
use any propagation at all (i.e. the algorithm should perform only
depth-first search in this case.)
To propagate a variable, call propagate with the specified enqueue_condition.
def solve_constraint_generic(problem, enqueue_condition=None) :
Answer the following question in your lab4.py file:
QUESTION 5: How many extensions does it take to solve the Pokemon problem 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) :
Also write one for being non-adjacent. There are trivial ways to do
it; feel free to call
def constraint_not_adjacent(m, n) :
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. Instead, write a function that takes a list of variables and returns a list containing, for each pair of variables, a constraint object requiring the variables to be different from each other. (You can model the constraints on the example above.) Note that order does NOT matter, so should only have one constraint between each pair of variables (ie (A,B) OR (B,A)).
def all_different(variables) :
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).
The moose problem can be found on 2008 Quiz 2, page 4. Use 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 insists on sitting in 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 which is 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
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
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, in alphabetical order.
- .domains: A dictionary associating each variable in the problem with its list of remaining values.
- .assigned_values: A dictionary. Each variable that has already been
assigned a value is associated with that value
here. When the problem is entirely solved,
assigned_valuescontains 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
Constraintobjects are described in the next section.
Note: 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) Returns the list of values in the variable's domain.
- csp.set_domain(var, domain) Sets the domain of the variable to the specified list of values, sorted alphabetically/numerically.
- csp.set_all_domains(domains_dict) Sets the .domains attribute to the specified dictionary. Does not sort domains.
- csp.get_all_variables() Returns a list of all the variables in the problem.
- csp.get_all_constraints() Returns a list of all the constraints in the problem.
- csp.pop_next_unassigned_var() Returns first unassigned variable, or None if all variables are assigned. Modifies unassigned_vars list.
- csp.set_unassigned_vars_order() Given an ordered list of unassigned variables, sets the list of unassigned vars. (By default, the unassigned_vars list is initialized in alphabetical order.)
- csp.eliminate(var, val) Removes the value from the variable's
domain. Note that as a helpful side-effect, this function returns
Trueif the value was found in the domain, or
Falseif the value wasn't found.
- csp.get_assigned_value(var) If the variable has been assigned a
value, retrieve it. Returns
Noneif the variable hasn't been assigned yet.
- csp.set_assigned_value(var, val) Sets 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. For convenience, also modifies the variable's domain to contain only the assigned value.
- csp.constraints_between(var1, var2)
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 involving
Xany any other variable, and
constraints_between(None, None)will return all of the constraints in the problem. Note: 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, constraint_fn)
Given two variables and a function to act as a constraint between them, creates a
Constraintobject and adds it to the list
csp.constraints. The function
constraint_fnmust take two arguments — a value for the first variable, and a value for the second variable — and return
Trueif the values satisfy the constraint, or
Add a list of
Constraintobjects to the list
csp.constraints. Useful for when you want to add several constraints to the problem at once, rather than one at a time using
- csp.copy() Return 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.
Constraint is a fairly basic object. It has three variables—
constraint_fn — and one method,
constraint.check(val1, val2) simply applies the
constraint function to the two arguments, returning
True if the
values satisfy the constraint, otherwise
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)
When you're done, run the online tester to submit your code.
(We'd ask which parts you find confusing, but if you're confused you should really ask a TA.)