Lab 3: Constraint Satisfaction

From 6.034 Wiki

(Difference between revisions)

Jump to: navigation, search

Current revision

This lab is due by Thursday, October 1 at 10:00pm.

1 A Working Vocabulary
2 Part 1: Warm-up
3 Part 2: Writing a depth-first search solver
- 3.1 Benchmarks
4 Part 3: Forward checking streamlines search by eliminating impossible assignments
- 4.1 Finding inconsistent values in neighbors
- 4.2 Depth-first constraint solver with forward checking
5 Part 4: Propagation!
- 5.1 Domain reduction
- 5.2 Propagation through reduced domains
6 Part 5A: Generic propagation
7 Part 5B: A generic constraint solver
8 Part 6: Defining your own constraints
9 API
- 9.1 Constraint Satisfaction Problems
- 9.2 Constraint objects
10 Appendix: Setting up a Constraint Satisfaction Problem
11 FAQ
12 Survey

Before working on the lab, you will need to get the code. You can...

Use Git on your computer: git clone username@athena.dialup.mit.edu:/mit/6.034/www/labs/fall2020/lab3

Use Git on Athena: git clone /mit/6.034/www/labs/fall2020/lab3

Download it as a ZIP file: http://web.mit.edu/6.034/www/labs/fall2020/lab3/lab3.zip

View the files individually: http://web.mit.edu/6.034/www/labs/fall2020/lab3/

All of your answers belong in the main file lab3.py. To submit your lab to the test server, you will need to download your key.py file and put it in either your lab3 directory or its parent directory. You can also view all of your lab submissions and grades here.

A Working Vocabulary

Before beginning, you may want to (re)familiarize yourself with the following terms:

variable: something that can receive an assignment value
value: something that can be assigned
domain: a set of values
constraint: a condition that limits domains of possible values

Part 1: Warm-up

In this lab, you'll write programs that solve constraint satisfaction problems (CSPs). A CSP consists of variables, assignments, and constraints, and is represented by a ConstraintSatisfactionProblem object as described in the API.

First, we'll get familiarity with CSPs by writing a few helper routines.

has_empty_domains(csp): returns True if the supplied problem has one or more empty domains. Otherwise, returns False.
check_all_constraints(csp): returns False if the problem's assigned values violate some constraint. Otherwise, returns True.

Each function takes in an argument csp, which is a ConstraintSatisfactionProblem instance.

Part 2: Writing a depth-first search solver

Now you can use your helper functions to write the constraint solver:

def solve_constraint_dfs(problem) :

This is just like depth-first search as implemented in the search lab, but this time the items in the agenda are partially-solved problems instead of paths. Additionally, for this problem, we will also want to track the number of extensions so we can compare the different strategies for constraint propagation. At the end, instead of returning just a solution, you will return a tuple (solution, num_extensions), where

solution is the solution to this problem as a dictionary mapping variables to assigned values (see API for details); or None if there is no solution to the problem.
num_extensions is the number of extensions performed during the search. Recall that as before, an extension occurs whenever a problem is removed from the agenda for processing.

Here is a rough outline of how to proceed:

Initialize your agenda and the extension count.
Until the agenda is empty, pop the first problem off the list and increment the extension count.
If any variable's domain is empty or if any constraints are violated, the problem is unsolvable with the current assignments.
If none of the constraints have been violated, check whether the problem has any unassigned variables. If not, you've found a complete solution!
However, if the problem has some unassigned variables:
1. Take the first unassigned variable off the list using csp.pop_next_unassigned_var().
2. For each value in the variable's domain, create a new problem with that value assigned to the variable, and add it to a list of new problems. Then, add the new problems to the appropriate end of the agenda.
Repeat steps 2 through 6 until a solution is found or the agenda is empty.

Benchmarks

So that we can compare the efficiency of different types of constraint-satisfaction algorithms, we'll compute how many extensions (agenda dequeues) each algorithm requires when solving a particular CSP. Our test problem will be the Pokemon problem from 2012 Quiz 2, pages 2-4.

You can solve the Pokemon problem by calling solve_constraint_dfs(pokemon_problem) directly. Note that the Pokemon problem is already defined for you in test_problems.py. To get a copy of it, use the method get_pokemon_problem() in lab4.py.

Please answer the following questions in your lab file:

Question 1: How many extensions does it take to solve the Pokemon problem with just DFS?

Put your answer (as an integer) in for ANSWER_1.

Part 3: Forward checking streamlines search by eliminating impossible assignments

One problem with the solve_constraint_dfs algorithm is that it explores all possible branches of the tree. We can use a trick called forward checking to avoid exploring branches that cannot possibly lead to a solution: each time we assign a value to a variable, we'll eliminate incompatible or inconsistent values from that variable's neighbors.

Finding inconsistent values in neighbors

First, we will write a helper function to eliminate inconsistent values from a variable's neighbors' domains:

Suppose V is a variable with neighbor W. If W's domain contains a value w which violates a constraint with every value in V's domain, then the assignment W=w can't be part of the solution we're constructing — we can safely eliminate w from W's domain.

(Note that unlike the check_all_constraints function above, eliminate_from_neighbors checks all combinations of values, and is not restricted to comparing only variables that have assigned values.)

This function should return an alphabetically sorted list of the neighbors whose domains were reduced (i.e. which had values eliminated from their domain), with each neighbor appearing at most once in the list. If no domains were reduced, return an empty list; if a domain is reduced to size 0, quit and immediately return None. This method should modify the input CSP. Hint: You can remove values from a variable's domain using csp.eliminate(var, val). But don't eliminate values from a variable while iterating over its domain, or Python will get confused!

def eliminate_from_neighbors(csp, var) :

We strongly suggest working out examples on paper to get a feel for how the forward checker should find inconsistent values.

To reduce the amount of nested for-loops and to make debugging easier, you may find it helpful to write a small helper function that, for example, takes in two variables V and W, and two values v and w in their respective domains, and checks if there are any constraint violations between V=v and W=w.

Depth-first constraint solver with forward checking

Now, we will write our improved CSP solver which uses eliminate_from_neighbors above to apply forward checking while searching for variable assignments.

def solve_constraint_forward_checking(problem) :

The implementation for this function will be very similar to that of solve_constraint_dfs, except now the solver must apply forward checking (eliminate_from_neighbors) after each assignment, to eliminate incompatible values from the assigned variable's neighbors.

Note that if eliminate_from_neighbors eliminates all values from a variable's domain, the problem will be recognized as unsolvable when it is next popped off the agenda: do not preemptively remove it from consideration.

Answer the following question in your lab4.py file:

Question 2: How many extensions does it take to solve the Pokemon problem with forward checking?

Put your answer (as an integer) in for ANSWER_2.

Part 4: Propagation!

Forward checking is a useful tool for checking ahead for inconsistencies and reducing the search space. However, in many situations, it's ideal to prune inconsistent states even faster.

Domain reduction

A far-reaching strategy called domain reduction eliminates incompatible values not just between neighbors, but across all variables in the problem. You can apply domain reduction either before search (this is what Sudoku players do when they narrow down options before tentatively guessing a value) or after assigning each variable during search (as a more powerful variation of forward-checking).

As it turns out, the implementation for both of these are effectively identical:

Establish a queue. If using domain reduction during search, this queue should initially contain only the variable that was just assigned. If before search (or if no queue is specified), the queue can contain all variables in the problem. (Hint: csp.get_all_variables() will make a copy of the variables list.)
Until the queue is empty, pop the first variable var off the queue.
Iterate over that var's neighbors: if some neighbor n has values that are incompatible with the constraints between var and n, remove the incompatible values from n's domain. If you reduce a neighbor's domain, add that neighbor to the queue (unless it's already in the queue).
If any variable has an empty domain, quit immediately and return None.
When the queue is empty, domain reduction has finished. 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.

Note that when the queue initially contains only the assigned variable, the first step of propagation is just forward checking of the assigned variable's neighbors. "Propagation" occurs as we add more variables to the queue, checking neighbors of neighbors, etc.

You will now implement domain_reduction, which applies forward checking (checking for neighboring values' inconsistencies) with propagation through any domains that are reduced.

Recall that domain reduction utilizes a queue to keep track of the variables whose neighbors should be explored for inconsistent domain values. If you are not explicitly provided a queue from the caller, your queue should start out with all of the problem's variables in it, in their default order.

When doing domain reduction, you should keep track of the order in which variables were dequeued; the function should return this ordered list of variables that were dequeued.

If at any point in the algorithm a domain becomes empty, immediately return None.

def domain_reduction(csp, queue=None) :

This method should modify the input CSP.

Hint: You can remove values from a variable's domain using csp.eliminate(var, val). But don't eliminate values from a variable while iterating over its domain, or Python will get confused!

Answer the following question in your lab4.py file:

Question 3: How many extensions does it take to solve the Pokemon problem with DFS (no forward checking) if you do domain reduction before solving it?

Put your answer (as an integer) in for ANSWER_3.

Propagation through reduced domains

Now we'll see how we can take advantage of domain reduction during the search procedure itself.

When used during search, domain reduction makes 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. After each assignment, propagation through reduced domains uses the domain_reduction subroutine to "propagate" the consequences of the assignment: to neighbors, then to neighbors of neighbors, and so on.

def solve_constraint_propagate_reduced_domains(problem) :

Note that if 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: do not preemptively remove it from consideration.

Debugging hint: be sure to look at the return types of functions that you call!

Answer the following question in your lab4.py file:

Question 4: How many extensions does it take to solve the Pokemon problem with forward checking and propagation through reduced domains? (Don't use domain reduction before solving it.)

Put your answer (as an integer) in for ANSWER_4.

Part 5A: Generic propagation

The domain_reduction 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 domain_reduction does, you can instead reduce only some of the domains. This idea underlies propagation through singleton domains — a reduction algorithm which does not detect as many dead ends, but which is significantly faster.

Instead of again patterning our propagation-through-singleton-domains algorithm off of domain_reduction, we'll write a fully general propagation algorithm called propagate that encapsulates all three checking strategies we've seen: forward checking, propagation through all reduced domains, and propagation through singleton domains.

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, a function that takes a problem and a variable, and outputs whether the variable should be added to the propagation queue.

def propagate(enqueue_condition_fn, 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.

As a review, propagation eliminates incompatible options from neighbors of variables in the queue. When used during search, the propagation queue initially contains only the just-assigned variable. The three enqueueing conditions we've seen are:

forward checking: never adds other variables to the queue
propagation through singleton domains: adds a neighboring variable to the queue if its domain has exactly one value in it
domain reduction / propagation through reduced domains: adds a neighboring variable to the queue if its domain has been reduced in size

Write functions that represent the enqueueing conditions (predicates) for each of these. Each predicate function below takes in a CSP and the variable in question, returning True if that variable should be added to the propagation queue, otherwise False.

 def condition_domain_reduction(csp, var) :

 def condition_singleton(csp, var) :

 def condition_forward_checking(csp, var) :

Part 5B: A generic constraint solver

Now, you can use propagate to write a generic constraint solver. Write an algorithm that can solve a problem using any enqueueing strategy. As a special case, if the enqueue_condition is None, default to ordinary dfs instead --- don't eliminate options from neighbors (don't use any forward checking or propagation) at all.

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 forward checking and propagation through singleton domains? (Don't use domain reduction before solving it.)

Put your answer (as an integer) in for ANSWER_5.

Part 6: Defining your own constraints

In this section, you will create some constraint functions yourself.

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.

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 for this particular constraint (the must-be-different constraint), order does NOT matter, because inequality is a symmetric relation. Hence, in you should only have one constraint between each pair of variables (e.g. have a constraint between A and B, OR have a constraint between B and A, but not both).

def all_different(variables) :

Note: You should only use constraint functions that have already been defined. Don't try to create a new constraint function and use it in this function, because our tester will get confused.

API

In this lab, we provide an API for representing and manipulating partial solutions to constraint satisfaction problems.

Constraint Satisfaction Problems

A ConstraintSatisfactionProblem is an object representing a partially solved constraint satisfaction problem. Its fields are:

variables: A list containing the names of all the variables in the problem, in alphabetical order.

domains: A dictionary associating each variable in the problem with its list of remaining values.

assignments: A dictionary. Each variable that has already been assigned a value is associated with that value here. When the problem is entirely solved, assignments contains the solution.

unassigned_vars: An ordered list of all the variables that still need to have a value assigned to them.

constraints: A list of the constraints between the variables in the problem. Each constraint is a Constraint object.

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:

get_domain(var): Returns the list of values in the variable's domain.

set_domain(var, domain): Sets the domain of the variable to the specified list of values, sorted alphabetically/numerically.

set_all_domains(domains_dict): Sets the domains field to the specified dictionary. Does not sort domains.

get_all_variables(): Returns a list of all the variables in the problem.

get_all_constraints(): Returns a list of all the constraints in the problem.

pop_next_unassigned_var(): Returns first unassigned variable, or None if all variables are assigned. Modifies unassigned_vars list.

set_unassigned_vars_order(unassigned_vars_ordered): Given an ordered list of unassigned variables, sets unassigned_vars. (By default, the unassigned_vars list is initialized in alphabetical order.)

eliminate(var, val): Removes the value from the variable's domain, returning True if the value was found in the domain, otherwise False if the value wasn't found.

get_assignment(var): If the variable has been assigned a value, retrieve it. Returns None if the variable hasn't been assigned yet.

set_assignment(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 var, or if var has already been assigned a value. For convenience, also modifies the variable's domain to contain only the assigned value.

constraints_between(var1, var2): Returns a list of all constraints between var1 and var2. Arguments that are None will match anything: for example, constraints_between('X',None) will return all constraints involving X and 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.

get_neighbors(var): Returns a list of all the variables that share constraints with the given variable, ordered alphabetically.

add_constraint(var1, var2, constraint_fn): Given two variables and a function to act as a constraint between them, creates a Constraint object and adds it to the constraints list. The function constraint_fn must be a binary predicate function: it takes two arguments (a value for the first variable, and a value for the second variable) and returns True if the values satisfy the constraint, or False otherwise.

add_constraints(list_of_constraints): Add a list of Constraint objects to the constraints list. Useful for when you want to add several constraints to the problem at once, rather than one at a time using .add_constraint.

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 CSP every time you assign a value to a variable.

Constraint objects

A Constraint is a fairly basic object representing a constraint between two variables. A Constraint object has three fields:

var1: The first variable associated with this constraint

var2: The second variable associated with this constraint

constraint_fn

A function that takes in two arguments, returning True or False depending on whether or not the given constraint is satisfied by the two arguments. For example,

constraint_equal(a, b) is a function requiring that a and b are equal.
constraint_different(a, b) is a function requiring that a and b are not equal.

These two functions are already defined in constraint_api.py, and can be accessed directly from lab4.py.

A Constraint object has just one method associated with it:

check(val1, val2): Applies this object's constraint_fn to two values (not variables), returning True if the values satisfy the constraint, or False otherwise.

Note: Due to certain limitations in our tester, a Constraint object constructor must take a named constraint_fn as an argument, NOT a lambda function.

Appendix: Setting up a Constraint Satisfaction Problem

The Pokemon problem from 2012 Quiz 2, pages 2-4, is an example of a problem that can be solved using constrained search.

In this section, we will show you how to convert this problem into a ConstraintSatisfactionProblem instance using our constraint satisfaction API.

To set up a problem, we first establish a new ConstraintSatisfactionProblem instance. For the Pokemon problem, there are five variables which we pass an an argument in a list: these are the five "questions" that need 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 named binary predicate (constraint function), not a lambda function:

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:

# How to set the order of unassigned variables (not actually used for the Pokemon problem)
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.

Note that the Pokemon problem is already defined for you in test_problems.py. To get a copy of it, use the method get_pokemon_problem() in lab4.py.

FAQ

Q: I am getting the right output but the wrong number of evaluations

A: Check that, when reducing domains, you are correctly considering the possibility of having multiple different constraints between two variables. (What does it mean if you have two contradictory constraints between two variables?)

Survey

Please answer these questions at the bottom of your lab file:

NAME: What is your name? (string)

COLLABORATORS: Other than 6.034 staff, whom did you work with on this lab? (string, or empty string if you worked alone)

HOW_MANY_HOURS_THIS_LAB_TOOK: Approximately how many hours did you spend on this lab? (number or string)

WHAT_I_FOUND_INTERESTING: Which parts of this lab, if any, did you find interesting? (string)

WHAT_I_FOUND_BORING: Which parts of this lab, if any, did you find boring or tedious? (string)

(optional) SUGGESTIONS: What specific changes would you recommend, if any, to improve this lab for future years? (string)

(We'd ask which parts you find confusing, but if you're confused you should really ask a TA.)

When you're done, run the online tester to submit your code.

Lab 3: Constraint Satisfaction

From 6.034 Wiki

Current revision

Contents

A Working Vocabulary

Part 1: Warm-up

Part 2: Writing a depth-first search solver

Benchmarks

Part 3: Forward checking streamlines search by eliminating impossible assignments

Finding inconsistent values in neighbors

Depth-first constraint solver with forward checking

Part 4: Propagation!

Domain reduction

Propagation through reduced domains

Part 5A: Generic propagation

Part 5B: A generic constraint solver

Part 6: Defining your own constraints

API

Constraint Satisfaction Problems

Constraint objects

Appendix: Setting up a Constraint Satisfaction Problem

FAQ

Survey

Views

Personal tools

Navigation

Search

Toolbox

@@ Line 1: / Line 1: @@
-__TOC__
+<!-- {{Unreleased}} -->
-This lab is due by Thursday, October 15 at 10:00pm.
+{{Lab_Due|when=Thursday, October 1}}
-'''Note:''' Online tests will be made available shortly.  In the meantime, the local tester provides thorough unit tests for each section of the lab.
+__TOC__
-To work on this lab, you will need to get the code, much like you did for the first two labs.
+{{Get_Code|lab=3}}
-* 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, <tt>add 6.034</tt> and copy it from <tt>/mit/6.034/www/labs/lab4/</tt>.
-Your answers for this lab belong in the main file <tt>lab4.py</tt>.
+== A Working Vocabulary ==
-<div id="outline-container-sec-1" class="outline-2">
+Before beginning, you may want to (re)familiarize yourself with the following terms:
-== Problems ==
+* '''variable''': something that can receive an assignment value
-<div class="outline-text-2" id="text-1">
+* '''value''': something that can be assigned
-</div><div id="outline-container-sec-1-1" class="outline-3">
+* '''domain''': a set of values
-=== Setting up a Constraint Satisfaction Problem ===
+* '''constraint''': a condition that limits domains of possible values
-<div class="outline-text-3" id="text-1-1">
-<p>
-Before beginning, you may want to familiarize yourself with the
-following terms: variable, value, domain, constraint, assignment.
-</p>
+== Part 1: Warm-up ==
-<p>
+In this lab, you'll write programs that solve constraint satisfaction problems (CSPs). A CSP consists of variables, assignments, and constraints, and is represented by a <tt>ConstraintSatisfactionProblem</tt> object as described in [[#API | the API]].
-Here is a problem that can be solved using constrained search:
-</p>
-<blockquote>
-<p>
-[e.g. insert the Pokemon problem here] todo
-The Pokemon problem is in sample_csp.py.
+First, we'll get familiarity with CSPs by writing a few helper routines.
-</p>
-</blockquote>
-<p>
+* <tt>has_empty_domains(csp)</tt>: returns <tt>True</tt> if the supplied problem has one or more empty domains. Otherwise, returns <tt>False</tt>.
-This part of the lab will show you how to convert this problem into a
+* <tt>check_all_constraints(csp)</tt>: returns <tt>False</tt> if the problem's <b>assigned values</b> violate some constraint. Otherwise, returns <tt>True</tt>.
-<code>ConstraintSatisfactionProblem</code> instance using our constraint
-satisfaction API.  The complete documentation is here: <a href="#sec-2">API Reference Documentation</a>.
-</p>
-<p>
+Each function takes in an argument <tt>csp</tt>, which is a [[#Constraint_Satisfaction_Problems|<tt>ConstraintSatisfactionProblem</tt>]] instance.
-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.
-</p>
-<p>
+== Part 2: Writing a depth-first search solver ==
-Here are definitions for the must-be-equal and must-not-be-equal
-constraint functions.  (These are defined in constraint_api.py.)
-</p>
+Now you can use your helper functions to write the constraint solver:
-  def constraint_equal(a,b) :
+  def solve_constraint_dfs(problem) :
-    return a == b
- def constraint_different(a,b) :
+This is just like depth-first search as implemented in the search lab, but this time the items in the agenda are partially-solved problems instead of paths. Additionally, for this problem, we will also want to track the number of extensions so we can compare the different strategies for constraint propagation. At the end, instead of returning just a solution, you will return a tuple <tt>(solution, num_extensions)</tt>, where
-    return a != b
+* <tt>solution</tt> is the solution to this problem as a dictionary mapping variables to assigned values (see API for details); or <tt>None</tt> if there is no solution to the problem.
+* <tt>num_extensions</tt> is the number of extensions performed during the search. Recall that as before, an extension occurs whenever a problem is <b>removed</b> from the agenda for processing.
+Here is a rough outline of how to proceed:
-<p>
+# Initialize your agenda and the extension count.
-To set up the problem, we first establish a new
+# Until the agenda is empty, pop the first problem off the list and increment the extension count.
-<code>ConstraintSatisfactionProblem</code> instance. There are five variables
+# If any variable's domain is empty or if any constraints are violated, the problem is ''unsolvable'' with the current assignments.
-which we pass an an argument in a list &#x2014; the five questions to be answered.
+# If none of the constraints have been violated, check whether the problem has any unassigned variables. If not, you've found a complete solution!
-</p>
+# However, if the problem has some unassigned variables:
+## Take the first unassigned variable off the list using <code>csp.pop_next_unassigned_var()</code>.
+## For each value in the variable's domain, create a new problem with that value assigned to the variable, and add it to a list of new problems. Then, add the new problems to the appropriate end of the agenda.
+# Repeat steps 2 through 6 until a solution is found or the agenda is empty.
-<div class="org-src-container">
+=== Benchmarks ===
-<pre class="src src-python" id="example-setup-vars">pokemon_problem = ConstraintSatisfactionProblem(["Q1","Q2","Q3","Q4","Q5"])
+So that we can compare the efficiency of different types of constraint-satisfaction algorithms, we'll compute how many extensions (agenda dequeues) each algorithm requires when solving a particular CSP. Our test problem will be the Pokemon problem from [http://courses.csail.mit.edu/6.034f/Examinations/2012q2.pdf 2012 Quiz 2], pages 2-4.
-</pre>
-</div>
-<p>
+You can solve the Pokemon problem by calling <tt>solve_constraint_dfs(pokemon_problem)</tt> directly. Note that the Pokemon problem is already defined for you in test_problems.py. To get a copy of it, use the method get_pokemon_problem() in lab4.py.
-Here, we specify the values  in each variable's domain.
-</p>
-<div class="org-src-container">
-<pre class="src src-python" id="example-setup-domains">pokemon_problem.set_domain("Q1",["A","B","C","D","E"])
+Please answer the following questions in your lab file:
-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"])
-</pre>
-</div>
+;Question 1
+:How many extensions does it take to solve the Pokemon problem with just DFS?
-<p>
+Put your answer (as an integer) in for <tt>ANSWER_1</tt>.
-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.)
-</p>
-<div class="org-src-container">
+== Part 3: Forward checking streamlines search by eliminating impossible assignments ==
-<pre class="src src-python">pokemon_problem.add_constraint("Q1","Q4", constraint_different)
+One problem with the <tt>solve_constraint_dfs</tt> algorithm is that it explores all possible branches of the tree. We can use a trick called forward checking to avoid exploring branches that cannot possibly lead to a solution: each time we assign a value to a variable, we'll eliminate incompatible or ''inconsistent'' values from that variable's neighbors.
-pokemon_problem.add_constraint("Q1","Q2", constraint_equal)
+=== Finding inconsistent values in neighbors ===
-pokemon_problem.add_constraint("Q3","Q2", constraint_different)
+First, we will write a helper function to eliminate ''inconsistent'' values from a variable's neighbors' domains:
-pokemon_problem.add_constraint("Q3","Q4", constraint_different)
+: Suppose V is a variable with neighbor W.  If W's domain contains a value w which violates a constraint with '''every value in V's domain''', then the assignment W=w can't be part of the solution we're constructing &mdash; we can safely eliminate w from W's domain.
-pokemon_problem.add_constraint("Q4","Q5", constraint_equal)
+(Note that unlike the <tt>check_all_constraints</tt> function above, <tt>eliminate_from_neighbors</tt> checks all combinations of values, and is not restricted to comparing only variables that have assigned values.)
-</pre>
-</div>
+<!-- :For a given neighbor <tt>n</tt> of a variable <tt>v</tt>, if <tt>n</tt> has a value <tt>nval</tt> that violates a constraint with every value in <tt>v</tt>'s domain, then <tt>nval</tt> is ''inconsistent'' with <tt>n</tt> and <tt>v</tt> and should be removed from <tt>n</tt>'s domain. !-->
-<p>
+This function should return an alphabetically sorted list of the neighbors whose domains were reduced (i.e. which had values eliminated from their domain), with each neighbor appearing '''at most once''' in the list. If no domains were reduced, return an empty list; if a domain is reduced to size 0, quit and immediately return <tt>None</tt>. This method '''should''' modify the input CSP. Hint: You can remove values from a variable's domain using csp.eliminate(var, val). But don't eliminate values from a variable while iterating over its domain, or Python will get confused!
-Finally, <code>csp.init_unassigned_vars</code> tells the problem which variables need
-to be assigned and in what order. If passed no argument, it simply
-includes all of the variables in the problem in some arbitrary order.
-</p>
-<div class="org-src-container">
+ def eliminate_from_neighbors(csp, var) :
-<pre class="src src-python">pokemon_problem.init_unassigned_vars()
+We strongly suggest working out examples on paper to get a feel for how the forward checker should find inconsistent values.
-</pre>
-</div>
-<p>
+To reduce the amount of nested for-loops and to make debugging easier, you may find it helpful to write a small helper function that, for example, takes in two variables V and W, and two values v and w in their respective domains, and checks if there are any constraint violations between V=v and W=w.
-Alternatively, you can also pass an argument to specify the order of the unassigned_vars yourself:
-</p>
-<div class="org-src-container">
+=== Depth-first constraint solver with forward checking ===
-<pre class="src src-python"># (An alternative, which we won't use here.)
+Now, we will write our improved CSP solver which uses <tt>eliminate_from_neighbors</tt> above to apply forward checking while searching for variable assignments.
-pokemon_problem.init_unassigned_vars(["Q4","Q2","Q3","Q1","Q5"])
-</pre>
-</div>
-<p>
-(For some problems, efficiently re-ordering of the variables can make
-a large difference in performance.)
-</p>
+ def solve_constraint_forward_checking(problem) :
+The implementation for this function will be very similar to that of <tt>solve_constraint_dfs</tt>, except now the solver must apply forward checking (<tt>eliminate_from_neighbors</tt>) after each assignment, to eliminate incompatible values from the assigned variable's neighbors.
-<p>
+Note that if <tt>eliminate_from_neighbors</tt> eliminates all values from a variable's domain, the problem will be recognized as unsolvable when it is ''next'' popped off the agenda: do not preemptively remove it from consideration.
-We have set up the variables, the domains, and the constraints. This
-problem is now ready to be solved &#x2014; all we need is a CSP solver.
-</p>
-</div>
-</div>
+Answer the following question in your <tt>lab4.py</tt> file:
-<div id="outline-container-sec-1-2" class="outline-3">
+;Question 2
-=== Writing a depth-first search solver ===
+:How many extensions does it take to solve the Pokemon problem with forward checking?
-<div class="outline-text-3" id="text-1-2">
-<p>
-Please write a constraint solver that uses <b>depth-first search</b> to
-find a solution.
-</p>
-<div class="org-src-container">
+Put your answer (as an integer) in for <tt>ANSWER_2</tt>.
-<pre class="src src-python">def solve_constraint_dfs(csp) :
+== Part 4: Propagation! ==
-    raise NotImplementedError
-</pre>
-</div>
+Forward checking is a useful tool for checking ahead for inconsistencies and reducing the search space. However, in many situations, it's ideal to prune inconsistent states even faster.
-<p>
+=== Domain reduction ===
-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.
-</p>
+A far-reaching strategy called ''domain reduction'' eliminates incompatible values not just between neighbors, but across all variables in the problem. You can apply domain reduction either ''before search'' (this is what Sudoku players do when they narrow down options before tentatively guessing a value) or ''after assigning each variable during search'' (as a more powerful variation of forward-checking).
+As it turns out, the implementation for both of these are effectively identical:
+# Establish a queue. If using domain reduction ''during'' search, this queue should initially contain only the variable that was just assigned. If before search (or if no queue is specified), the queue can contain all variables in the problem.  (Hint: <tt>csp.get_all_variables()</tt> will make a copy of the variables list.)
+# Until the queue is empty, pop the first variable <tt>var</tt> off the queue.
+# Iterate over that <tt>var</tt>'s neighbors: if some neighbor <tt>n</tt> has values that are incompatible with the constraints between <tt>var</tt> and <tt>n</tt>, remove the incompatible values from <tt>n</tt>'s domain. If you reduce a neighbor's domain, add that neighbor to the queue (unless it's already in the queue).
+# If any variable has an empty domain, quit immediately and return <tt>None</tt>.
+# When the queue is empty, domain reduction has finished. 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.
+Note that when the queue initially contains only the assigned variable, the first step of propagation is just forward checking of the assigned variable's neighbors. "Propagation" occurs as we add more variables to the queue, checking neighbors of neighbors, etc.
-<p>
-Here is a rough outline of how to proceed:
-</p>
-<ol class="org-ol">
+You will now implement <tt>domain_reduction</tt>, which applies forward checking (checking for neighboring values' inconsistencies) with propagation through any domains that are reduced.
-<li><p>
-Create an agenda containing only the problem <code>csp</code>.
-</p>
-</li>
-<li><p>
-Until the agenda is empty, pop the first problem off the list.
-</p>
-</li>
-<li><p>
-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.)
-</p>
-</li>
-<li><p>
-If none of the constraints have been violated, check whether the
-problem has any unassigned variables (<code>csp.unassigned_vars</code>). If
-the problem has no unassigned variables, you've found a complete
-solution!  Return the assignments (<code>csp.assigned_value</code>).
-The return type should be a tuple <code>(solution, extension_count)</code>, containing:
+Recall that domain reduction utilizes a queue to keep track of the variables whose neighbors should be explored for inconsistent domain values. If you are not explicitly provided a queue from the caller, your queue should start out with all of the problem's variables in it, in their default order.
-# the solution (csp.assigned_value, which is a dictionary mapping variables to assigned values), and
-# the number of extensions made (the number of problems popped off the agenda).
-If no solution was found, return None as the first element of the tuple, instead of the solution.
+When doing domain reduction, you should keep track of the order in which variables were dequeued; the function should return this ordered list of variables that were dequeued.
-Note: extensions is the number of nodes popped off the agenda (dequeued), #todo format
+If at any point in the algorithm a domain becomes empty, immediately return <tt>None</tt>.
-including root (original problem), csps with children, csps with no children,
-and final csp (which has all vars assigned)
-</p>
+ def domain_reduction(csp, queue=None) :
-</li>
-<li><p>
-If the problem has some unassigned variables:
-</p>
-<ul class="org-ul">
-<li>Take the first unassigned variable off the list
-(csp.unassigned_vars).
-</li>
-<li>For each value in the variable's domain (csp.get_domain(var)),
-create a new copy of the problem. (csp_new = csp.copy()).
-</li>
-<li>Using the copy, assign the value to the variable. (
-<code>csp_new.set_assigned_value(var, val)</code> ).
-</li>
-<li>Collect the list of copies and add the list to the front of the
-agenda (as is appropriate for depth-first search).
-</li>
-</ul>
-</li>
-</ol>
+This method '''should''' modify the input CSP.
-<p>
+Hint: You can remove values from a variable's domain using <tt>csp.eliminate(var, val)</tt>. But '''don't''' eliminate values from a variable while iterating over its domain, or Python will get confused!
-These are helper functions that you can use within
-<code>solve_constraint_dfs</code>.
-def has_empty_domains(csp): #todo format
+Answer the following question in your <tt>lab4.py</tt> file:
-    "Returns True if csp has one or more empty domains, otherwise False"
-    return not all(csp.domains.values())
+;Question 3
+:How many extensions does it take to solve the Pokemon problem with DFS (no forward checking) if you do domain reduction before solving it?
-check_all_assignments should return False if the problem's
+Put your answer (as an integer) in for <tt>ANSWER_3</tt>.
-assigned values violate some constraint, otherwise True.
-</p>
-<div class="org-src-container">
+=== Propagation through reduced domains ===
-<pre class="src src-python">def check_all_assignments(problem) :
+Now we'll see how we can take advantage of domain reduction during the search procedure itself.
-    raise NotImplementedError
-</pre>
-</div>
-</div>
-</div>
+When used during search, domain reduction makes 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.  After each assignment, propagation through reduced domains uses the domain_reduction subroutine to "propagate" the consequences of the assignment: to neighbors, then to neighbors of neighbors, and so on.
-<div id="outline-container-sec-1-3" class="outline-3">
+ def solve_constraint_propagate_reduced_domains(problem) :
-=== Domain reduction before search ===
-<div class="outline-text-3" id="text-1-3">
-<p>
-Domain reduction is a strategy for eliminating impossible values in
-advance to cut down on the amount of search you have to do.
-</p>
-<p>
+Note that if <tt>domain_reduction</tt> eliminates all values from a variable's domain, the problem will be recognized as unsolvable when it is ''next'' popped off the agenda: do not preemptively remove it from consideration.
-First, write a helper function to eliminate values from a variable's neighbors' domains.
-Each variable should
-appear AT MOST ONCE in the list; the list should
-contain no duplicates.
-</p>
-<p>
+Debugging hint: be sure to look at the return types of functions that you call!
-Hint: csp.constraints_between may help.
-</p>
-def eliminate_from_neighbors(csp, var) :  #todo format (move docstring up to description)
+Answer the following question in your <tt>lab4.py</tt> file:
-    """Eliminates incompatible values from var's neighbors' domains, modifying
-    the original csp.  Returns alphabetically sorted list of the neighboring
-    variables whose domains were reduced, with each variable appearing at most
-    once.  If no domains were reduced, returns empty list.  If a domain is
-    reduced to size 0, quits and returns None."""
-<p>
+;Question 4
-Next, you will need to write a domain-reduction algorithm.
+:How many extensions does it take to solve the Pokemon problem with forward checking and propagation through reduced domains? (Don't use domain reduction before solving it.)
-</p>
-<div class="org-src-container">
+Put your answer (as an integer) in for <tt>ANSWER_4</tt>.
-<pre class="src src-python">def domain_reduction(csp, queue=None) :
+== Part 5A: Generic propagation ==
-    raise NotImplementedError
-</pre>
-</div>
-<p>
+The <tt>domain_reduction</tt> 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.
-Here is a rough description of the domain reduction algorithm:
-</p>
-<ol class="org-ol">
-<li>Establish a queue &#x2014; if the optional argument <code>queue</code> was passed
-as an argument, use that as your queue. Otherwise, <code>queue</code> should
-consist of all the variables in the problem.
-</li>
-<li>Until the queue is empty, pop the first variable off the queue. <!-- todo should 'pop' be 'dequeue'?  does it matter? (probably not.) -->
-</li>
-<li>Iterate over the variable's constraints: if a neighbor has a value
-that violates a constraint with <i>every</i> value in the variable's
-domain, remove the neighbor's value and add the neighbor to the
-queue ''if and only if the neighbor is not already in queue''<sup><a id="fnr.1" class="footref" href="#fn.1">1</a></sup>.
-</li>
-<li>If any variable has an empty domain, quit immediately and return
-None.
-</li>
-<li>If the queue is empty, domain reduction has finished. As a
-side-effect, please return:
-    """Uses constraints to reduce domains, modifying the original csp. #todo format
+Instead of comprehensively reducing all the domains in a problem, as <tt>domain_reduction</tt> does, you can instead reduce only ''some'' of the domains. This idea underlies ''propagation through singleton domains'' — a reduction algorithm which does not detect as many dead ends, but which is significantly faster.
-    If queue is None, initializes propagation queue by adding all variables in
-    alphabetical order.  Returns a list of all variables that were dequeued,
-    in the order they were removed from the queue.  Variables may appear in the
-    list multiple times.
-    If a domain is reduced to size 0, quits immediately and returns None."""
-break any ties lexicographically (probably natural)
+Instead of again patterning our propagation-through-singleton-domains algorithm off of <tt>domain_reduction</tt>, we'll write a fully general propagation algorithm called <tt>propagate</tt> that encapsulates all three checking strategies we've seen: forward checking, propagation through all reduced domains, and propagation through singleton domains.
-</li>
-</ol>
-<p>
-Hint: You can remove values from a variable's domain using <code>csp.eliminate(var, val)</code>.
-(But don't eliminate values from a variable while iterating over its domain, or Python will get confused.)
-</p>
+The function <code>propagate</code> will be similar to the propagation algorithms you've already defined. The difference is that it will take an argument <tt>enqueue_condition_fn</tt>, a function that takes a problem and a variable, and outputs whether the variable should be added to the propagation queue.
-</div>
+ def propagate(enqueue_condition_fn, csp, queue = None) :
-<div id="outline-container-sec-1-3-1" class="outline-4">
+Propagation through singletons is like propagation through reduced domains, except that variables must pass a test in order to be added to the queue:
-<h4 id="sec-1-3-1"> Benchmarks</h4>
+:In propagation through singleton domains, you only append a variable to the queue if it has exactly one value left in its domain.
-<div class="outline-text-4" id="text-1-3-1">
-<p>
-You can solve the pokemon problem by calling
-<code>solve_constraint_dfs(pokemon_problem)</code> directly. Using domain
-reduction first, however, should make search faster. Please answer the
-following questions in your lab file:
-</p>
-# QUESTION 1: How many extensions does it take to solve the Pokemon problem #todo format
+'''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.
-#    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
+As a review, propagation eliminates incompatible options from neighbors of variables in the queue. When used during search, the propagation queue initially contains only the just-assigned variable. The three enqueueing conditions we've seen are:
+# ''forward checking'': never adds other variables to the queue
+# ''propagation through singleton domains'': adds a neighboring variable to the queue if its domain has exactly one value in it
+# ''domain reduction / propagation through reduced domains'': adds a neighboring variable to the queue if its domain has been reduced in size
-# QUESTION 2: How many extensions does it take to solve the Pokemon problem
+Write functions that represent the enqueueing conditions (predicates) for each of these. Each predicate function below takes in a CSP and the variable in question, returning <tt>True</tt> if that variable should be added to the propagation queue, otherwise <tt>False</tt>.
-#    with dfs if you DO use domain reduction before solving it?
+<pre>
+ def condition_domain_reduction(csp, var) :
-ANSWER_2 = None
+ def condition_singleton(csp, var) :
-</div>
-</div>
-</div>
+ def condition_forward_checking(csp, var) :
-<div id="outline-container-sec-1-4" class="outline-3">
-=== Propagation through reduced domains ===
-<div class="outline-text-3" id="text-1-4">
-<p>
-Domain reduction can be used not only before search, but also <i>during</i>
-search. When used during search, domain reduction can make use of the
-assignments you've made to progressively reduce the search space. The
-result is a new, faster, csp solution method: propagation through
-reduced domains.
-</p>
-<div class="org-src-container">
-<pre class="src src-python">def solve_constraint_propagate_reduced_domains(problem) :
-    raise NotImplementedError
 </pre>
-</div>
-<p>
+== Part 5B: A generic constraint solver ==
-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 <code>domain_reduction</code> function with the assigned variable
-as an argument. If the <code>domain_reduction</code> function returns
-<code>None</code>, the problem can't be solved with the given assignments &#x2014;
-don't add the problem to the agenda. Otherwise, add the problem to the
-agenda as usual.
-</p>
-Note: domain_reduction should remove values from the assigned variable's ''neighbors' ''domains, not from the variable's domain.
+Now, you can use <tt>propagate</tt> to write a generic constraint solver. Write an algorithm that can solve a problem using any enqueueing strategy. As a special case, if the <tt>enqueue_condition</tt> is <code>None</code>, default to ordinary dfs instead --- don't eliminate options from neighbors (don't use any forward checking or propagation) at all.
-</div>
+ def solve_constraint_generic(problem, enqueue_condition=None) :
-</div>
-Answer the following question in your lab4.py file:
+Answer the following question in your <tt>lab4.py</tt> file:
-# QUESTION 3: How many extensions does it take to solve the Pokemon problem #todo format
+;Question 5
-#    with propagation through reduced domains? (Don't use domain reduction
+:How many extensions does it take to solve the Pokemon problem with forward checking and propagation through singleton domains? (Don't use domain reduction before solving it.)
-#    before solving it.)
-ANSWER_3 = None
+Put your answer (as an integer) in for <tt>ANSWER_5</tt>.
-<div id="outline-container-sec-1-5" class="outline-3">
+== Part 6: Defining your own constraints ==
-=== Propagation through singleton domains ===
+In this section, you will create some constraint functions yourself.
-<div class="outline-text-3" id="text-1-5">
-<p>
-The <code>reduce_domains</code> 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 <i>before</i> solving a constraint satisfaction problem, but is often
-too expensive to call repeatedly during search.
-</p>
-<p>
+Assuming <tt>m</tt> and <tt>n</tt> are integers, write a function that returns <tt>True</tt> if <tt>m</tt> and <tt>n</tt> are adjacent values (i.e. if they differ by exactly one) and <tt>False</tt> otherwise.
-Instead of comprehensively reducing all the domains in a problem, as
-<code>reduce_domains</code> does, you can instead reduce only <i>some</i> of the
-domains. This results in <i>propagation through singleton domains</i> &#x2014; a
-reduction algorithm which does not detect as many dead ends, but which
-is significantly faster.
-</p>
-<div class="org-src-container">
+ def constraint_adjacent(m, n) :
-<pre class="src src-python">def domain_reduction_singleton_domains(csp, queue=None) :
+Also write one for being non-adjacent.
-    raise NotImplementedError
-</pre>
-</div>
-<p>
+ def constraint_not_adjacent(m, n) :
-Propagation through singletons is like propagation through reduced
-domains, except that variables must pass a test in order to be added
-to the queue:
-</p>
-<blockquote>
+The following example shows how you build a constraint object that requires two variables — call them A and B — to be different.
-<p>
-In propagation through singleton domains, you only append a variable
-to the queue if it has exactly one value left in its domain.
-</p>
-</blockquote>
-<p>
+ example_constraint = Constraint("A","B", constraint_different)
-<b>Common misconception</b>: Please note that propagation never <i>assigns</i>
-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.
-</p>
-</div>
-</div>
-Then write:
+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 for this ''particular'' constraint (the must-be-different constraint), order does NOT matter, because inequality is a symmetric relation. Hence, in you should only have ''one'' constraint between each pair of variables (e.g. have
+a constraint between A and B, '''OR''' have a constraint between B and A, but not both).
-def solve_constraint_propagate_singleton_domains(problem) : #todo formatting
+ def all_different(variables) :
-    """Solves the problem using depth-first search with forward checking and
-    propagation through singleton domains.  Same return type as
-    solve_constraint_dfs."""
-    raise NotImplementedError
-and answer:
+Note: You should only use constraint functions that have already been defined. Don't try to create a new constraint function and use it in this function, because our tester will get confused.
-# QUESTION 4: How many extensions does it take to solve the Pokemon problem #todo format
+<!-- Future ideas:
-#    with propagation through singleton domains? (Don't use domain reduction
+=== Resource allocation ===
-#    before solving it.)
+Find out what size domain you need using binary search.
-ANSWER_4 = None
+=== Counting solutions ===
+Use "yield" to count the number of solutions.
-<div id="outline-container-sec-1-6" class="outline-3">
+<h4 id="sec-1-7-1"> Comparing propagation strategies</h4>
-=== Forward checking ===
-<div class="outline-text-3" id="text-1-6">
-<p>
-Forward checking is even more restrictive than propagation through
-singletons: it <i>never</i> 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.)
-</p>
-<p>
-Instead of patterning our forward checking algorithm off of
-<code>domain_reduction</code> again, we'll write a fully general algorithm called
-<code>propagate</code> that encapsulates all three propagation strategies we've
-seen: propagation through reduced domains, propagation through
-singletons, and forward checking.
-</p>
-<p>
-The function <code>propagate</code> will be similar to the propagation algorithms
-you've already defined. The difference is that it will take an
-argument <code>enqueue_condition_fn</code> which is the test that variables must
-pass in order to be added to the queue: before <code>propagate</code> adds a
-variable to the queue, it should call <code>enqueue_condition_fn(csp, var)</code>
-. If the function returns <code>True</code>, it should add the variable to the
-queue. Otherwise, it shouldn't.
-</p>
-<div class="org-src-container">
-<pre class="src src-python">def propagate(enqueue_condition_fn, csp, queue = None) :
-    raise NotImplementedError
-</pre>
-</div>
-<p>
-To review, the three enqueueing conditions we've seen are:
-</p>
-<dl class="org-dl">
-<dt>domain reduction</dt><dd>always add the variable to the queue
-</dd>
-<dt>singleton propagation</dt><dd>add the variable if its domain has exactly
-one value in it.
-</dd>
-<dt>forward checking</dt><dd>never add the variable to the queue.
-</dd>
-</dl>
-<p>
-Write functions for each of these tests. Hint: some of these
-functions may ignore some of their arguments.
-</p>
-<div class="org-src-container">
-<pre class="src src-python">def condition_domain_reduction(csp, var) :
-    raise NotImplementedError
-def condition_singleton(csp, var) :
-    raise NotImplementedError
-def condition_forward_checking(csp, var) :
-    raise NotImplementedError
-</pre>
-</div>
-<p>
-And thus we can define:
-</p>
-<div class="org-src-container">
-<pre class="src src-python">domain_reduction_forward_checking =
-lambda csp, queue=None: propagate(condition_forward_checking, csp, queue)
-</pre>
-</div>
-</div>
-</div>
-<div id="outline-container-sec-1-7" class="outline-3">
-=== A generic CSP solver ===
-<div class="outline-text-3" id="text-1-7">
-<p>
-Write an algorithm that can solve a problem using any enqueueing
-strategy. As a special case, if the enqueue_condition is <code>None</code>, don't
-use any propagation at all (i.e. the algorithm should perform only
-depth-first search in this case.)
-</p>
-<div class="org-src-container">
-<pre class="src src-python">def solve_constraint_generic(problem, enqueue_condition=None) :
-    raise NotImplementedError
-</pre>
-</div>
-</div>
-    """Solves the problem, calling propagate with the specified enqueue #todo formatting
-    condition (a function).  If enqueue_condition is None, uses DFS only.
-    Same return type as solve_constraint_dfs."""
-Answer:
-# QUESTION 5: How many extensions does it take to solve the Pokemon problem #todo formatting
-#    with DFS and forward checking, but no propagation? (Don't use domain
-#    reduction before solving it.)
-ANSWER_5 = None
-<!--
-<div id="outline-container-sec-1-7-1" class="outline-4">
-<h4 id="sec-1-7-1"> TODO Comparing propagation strategies</h4>
-<div class="outline-text-4" id="text-1-7-1">
-<p>
 Including the trouble with texas.
-</p>
-</div>
-</div>
-<div id="outline-container-sec-1-7-2" class="outline-4">
+<h4 id="sec-1-7-2"> Variable re-ordering</h4>
-<h4 id="sec-1-7-2"> TODO Variable re-ordering</h4>
-<div class="outline-text-4" id="text-1-7-2">
-<p>
 How should you order your variables in the agenda? e.g.
-</p>
 <ul class="org-ul">
 <li>most constrained variables first
@@ Line 599: / Line 244: @@
 </ul>
-<p>
 Let's find out empirically.
-</p>
-</div>
-</div>
-</div>
 -->
+== API ==
+In this lab, we provide an API for representing and manipulating partial solutions to constraint satisfaction problems.
+=== Constraint Satisfaction Problems ===
-<div id="outline-container-sec-1-8" class="outline-3">
+A <tt>ConstraintSatisfactionProblem</tt> is an object representing a partially solved constraint satisfaction problem. Its fields are:
-=== Solving your own CSPs ===
+;<tt>variables</tt>
-<div class="outline-text-3" id="text-1-8">
+:A list containing the names of all the variables in the problem, in alphabetical order.
-</div><div id="outline-container-sec-1-8-1" class="outline-4">
-<h4 id="sec-1-8-1"> Defining new constraints</h4>
-<div class="outline-text-4" id="text-1-8-1">
-<p>
-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.
-</p>
-<div class="org-src-container">
+;<tt>domains</tt>
+:A dictionary associating each variable in the problem with its list of remaining values.
-<pre class="src src-python">def constraint_adjacent(m, n) :
+;<tt>assignments</tt>
-    raise NotImplementedError
+:A dictionary. Each variable that has already been assigned a value is associated with that value here. When the problem is entirely solved, <tt>assignments</tt> contains the solution.
-</pre>
-</div>
-<p>
+;<tt>unassigned_vars</tt>
-Also write one for being non-adjacent. There are simple ways to do
+:An ordered list of all the variables that still need to have a value assigned to them.
-it; feel free to call <code>constraint_adjacent</code>.
-</p>
-<div class="org-src-container">
+;<tt>constraints</tt>
+:A list of the constraints between the variables in the problem. Each constraint is a <tt>Constraint</tt> object.
-<pre class="src src-python">def constraint_not_adjacent(m, n) :
+Note: While you may ''read'' any of the above variables, you should probably not modify them directly;<tt> instead, you should use the following API methods:</tt>
-    raise NotImplementedError
-</pre>
-</div>
+;<tt>get_domain(var)</tt>
+:Returns the list of values in the variable's domain.
-<p>
+;<tt>set_domain(var, domain)</tt>
-The following example shows how you build a constraint object that
+:Sets the domain of the variable to the specified list of values, sorted alphabetically/numerically.
-requires two variables &#x2014; call them A and B &#x2014; to be different.
-</p>
-<div class="org-src-container">
+;<tt>set_all_domains(domains_dict)</tt>
+:Sets the <tt>domains</tt> field to the specified dictionary. Does not sort domains.
-<pre class="src src-python">example_constraint = Constraint("A","B", constraint_different)
+;<tt>get_all_variables()</tt>
-</pre>
+:Returns a list of all the variables in the problem.
-</div>
-<p>
+;<tt>get_all_constraints()</tt>
-Some constraint problems include a constraint that requires all of
+:Returns a list of all the [[#Constraint_objects | constraints]] in the problem.
-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).
-</p>
-<div class="org-src-container">
+;<tt>pop_next_unassigned_var()</tt>
+:Returns first unassigned variable, or <tt>None</tt> if all variables are assigned. Modifies <tt>unassigned_vars</tt> list.
-<pre class="src src-python">def all_different(vars) :
+;<tt>set_unassigned_vars_order(unassigned_vars_ordered)</tt>
-    raise NotImplementedError
+:Given an ordered list of unassigned variables, sets <tt>unassigned_vars</tt>. (By default, the <tt>unassigned_vars</tt> list is initialized in alphabetical order.)
-</pre>
-</div>
-</div> <!--todo omg why are there so many html tags everywhere-->
-</div>
-<div id="outline-container-sec-1-8-2" class="outline-4">
+;<tt>eliminate(var, val)</tt>
-<h4 id="sec-1-8-2"> Defining a new problem</h4>
+:Removes the value from the variable's domain, returning <tt>True</tt> if the value was found in the domain, otherwise <tt>False</tt> if the value wasn't found.
-<div class="outline-text-4" id="text-1-8-2">
-<p>
-Design and solve a constraint satisfaction problem for the following
-word problem.
-</p>
-<p>
+;<tt>get_assignment(var)</tt>
-! You will need some new constraint functions.
+:If the variable has been assigned a value, retrieve it. Returns <tt>None</tt> if the variable hasn't been assigned yet.
-</p>
-<blockquote>
+;<tt>set_assignment(var, val)</tt>
-<p>
+:Sets the assigned value of the variable to <tt>val</tt>, returning a modified copy of the constraint satisfaction problem. Throws an error if <tt>val</tt> is not in the domain of <tt>var</tt>, or if <tt>var</tt> has already been assigned a value. For convenience, also modifies the variable's domain to contain only the assigned value.
-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?
-</p>
-</blockquote>
+;<tt>constraints_between(var1, var2)</tt>
+:Returns a list of all [[#Constraint_objects | constraints]] between <tt>var1</tt> and <tt>var2</tt>. Arguments that are <tt>None</tt> will match anything: for example, <tt>constraints_between('X',None)</tt> will return all constraints involving <tt>X</tt> and any other variable, and <tt>constraints_between(None, None)</tt> 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, <tt>csp.constraints_between(None, 'Y')</tt> will return a list of all constraints involving <tt>'Y'</tt> — and the constraints will be altered so that <tt>'Y'</tt> is their ''second'' variable (<tt>var2</tt>) in every case.
-<p>
+;<tt>get_neighbors(var)</tt>
-Interpret constraints that only mention one person (e.g. "Baker
+:Returns a list of all the variables that share constraints with the given variable, ordered alphabetically.
-does not live on the top floor.") as an indication that you should
-leave out those values from the variable's domain &#x2014; you won't
-need to make a constraint to represent those kinds of constraints.
-</p>
-<div class="org-src-container">
+;<tt>add_constraint(var1, var2, constraint_fn)</tt>
+:Given two variables and a function to act as a constraint between them, creates a [[#Constraint_objects | <tt>Constraint</tt> object]] and adds it to the <tt>constraints</tt> list. The function <tt>constraint_fn</tt> must be a binary predicate function: it takes two arguments (a value for the first variable, and a value for the second variable) and returns <tt>True</tt> if the values satisfy the constraint, or <tt>False</tt> otherwise.
-<pre class="src src-python">apartment_problem = ConstraintSatisfactionProblem(["Baker", "Cooper", "Fletcher", "Miller", "Smith"])
+;<tt>add_constraints(list_of_constraints)</tt>
-</pre>
+:Add a list of [[#Constraint_objects | <tt>Constraint</tt> objects]] to the <tt>constraints</tt> list. Useful for when you want to add several constraints to the problem at once, rather than one at a time using <code>.add_constraint</code>.
-</div>
+;<tt>copy()</tt>
+:Return a (deep) copy of this constraint satisfaction problem. This method is particularly useful because you will want to make a copy of the CSP every time you assign a value to a variable.
-<p>
+=== Constraint objects ===
-Establish the domains of the variables. Each variable will have a
-domain that's a subset of [1,2,3,4,5].
-</p>
-<p>
+A <tt>Constraint</tt> is a fairly basic object representing a constraint between two variables. A <tt>Constraint</tt> object has three fields:
-Establish the constraints. Remember the constraint that says that
-all of the variables must be assigned a different value. You may
-want to use <code>csp.add_constraints(list)</code>.
-</p>
-</div>
-</div>
-</div>
+;<tt>var1</tt>
+:The first variable associated with this constraint
+;<tt>var2</tt>
+:The second variable associated with this constraint
+;<tt>constraint_fn</tt>
+:A function that takes in two arguments, returning <tt>True</tt> or <tt>False</tt> depending on whether or not the given constraint is satisfied by the two arguments. For example,
+:* <tt>constraint_equal(a, b)</tt> is a function requiring that <tt>a</tt> and <tt>b</tt> are equal.
+:* <tt>constraint_different(a, b)</tt> is a function requiring that <tt>a</tt> and <tt>b</tt> are not equal.
+:These two functions are already defined in <tt>constraint_api.py</tt>, and can be accessed directly from <tt>lab4.py</tt>.
-<div id="outline-container-sec-1-9" class="outline-3">
+----
-=== TODO Resource allocation ===
+A <tt>Constraint</tt> object has just one method associated with it:
-<div class="outline-text-3" id="text-1-9">
-<p>
-Find out what size domain you need using binary search.
-</p>
-</div>
-</div>
+;<tt>check(val1, val2)</tt>
+:Applies this object's <tt>constraint_fn</tt> to two ''values'' ('''not''' variables), returning <tt>True</tt> if the values satisfy the constraint, or <tt>False</tt> otherwise.
-<div id="outline-container-sec-1-10" class="outline-3">
+'''Note:''' Due to certain limitations in our tester, a <code>Constraint</code> object constructor must take a '''named''' <code>constraint_fn</code> as an argument, '''NOT''' a lambda function.
-=== TODO Counting solutions ===
-<div class="outline-text-3" id="text-1-10">
-<p>
-Use "yield" to count the number of solutions.
-</p>
-</div>
-</div>
-</div>
+== Appendix: Setting up a Constraint Satisfaction Problem ==
+The Pokemon problem from [http://courses.csail.mit.edu/6.034f/Examinations/2012q2.pdf 2012 Quiz 2], pages 2-4, is an example of a problem that can be solved using constrained search.
-<div id="outline-container-sec-2" class="outline-2">
+In this section, we will show you how to convert this problem into a <tt>ConstraintSatisfactionProblem</tt> instance using our [[#API|constraint satisfaction API]].
-== API Reference Documentation ==
+To set up a problem, we first establish a new <code>ConstraintSatisfactionProblem</code> instance. For the Pokemon problem, there are five variables which we pass an an argument in a list: these are the five "questions" that need to be answered.
-<div class="outline-text-2" id="text-2">
-<p>
-In this lab, we provide an API for representing and
-manipulating partial solutions to constraint satisfaction problems.
+ pokemon_problem = ConstraintSatisfactionProblem(["Q1","Q2","Q3","Q4","Q5"])
-<!--
+Here, we specify the values in each variable's domain:
-A <tt>ConstraintSatisfactionProblem</tt> object encodes the state of a partially-solved problem; these are the nodes in your search tree when you are performing constrained search by hand.
-!-->
-</p>
+<pre>
-</div>
+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"])
+</pre>
+Next, we set up constraints. Each constraint takes two variable names, and a ''named'' [[#API|binary predicate]] (constraint function), not a lambda function:
-<div id="outline-container-sec-2-1" class="outline-3">
+<pre>
-=== Constraint Satisfaction Problems ===
+pokemon_problem.add_constraint("Q1","Q4", constraint_different)
-<div class="outline-text-3" id="text-2-1">
+pokemon_problem.add_constraint("Q1","Q2", constraint_equal)
-<p>
+pokemon_problem.add_constraint("Q3","Q2", constraint_different)
-A <code>ConstraintSatisfactionProblem</code> is an object representing a
+pokemon_problem.add_constraint("Q3","Q4", constraint_different)
-partially-solved constraint satisfaction problem. Its fields are:
+pokemon_problem.add_constraint("Q4","Q5", constraint_equal)
-</p>
+</pre>
+By default, the <tt>unassigned_vars</tt> list is initialized in alphabetical order.
-<ul>
+To specify the order yourself, you can call <tt>.set_unassigned_vars_order</tt> with an ordered list of the unassigned variables:
-<li>'''variables'''
-<span></span>A list containing the names of all the variables in the problem.
-</li>
-<li>'''domains''' <span></span>A dictionary associating each variable in the problem with
-its list of remaining values so far<sup><a id="fnr.2" class="footref" href="#fn.2">2</a></sup>.
-</li>
-<li>'''assigned_values''' <span></span>A dictionary. Each variable which has already been
-assigned a value is associated with that value
-here. When the problem is entirely solved,
-<code>assigned_value</code> contains the solution.
-</li>
-<li>'''unassigned_vars''' <span></span>An ordered list of all the variables that still
-need to have a value assigned to them.
-</li>
-<li>'''constraints''' <span></span>A list of the constraints between the variables in
-the problem. Each constraint is a <code>Constraint</code>
-object; <code>Constraint</code> objects are described in the
-next section.
-</li>
-</ul>
-<p>
+<pre>
-Please note that while you may <i>read</i> any of the above variables, you
+# How to set the order of unassigned variables (not actually used for the Pokemon problem)
-should probably not modify them directly; instead, you should use the
+pokemon_problem.set_unassigned_vars_order(["Q4","Q2","Q3","Q1","Q5"])
-following API methods. (Below, <code>csp</code> stands for some
+</pre>
-<code>ConstraintSatisfactionProblem</code> instance that you want to manipulate.)
-</p>
-<ul>
+For some problems, efficiently re-ordering the variables can make a large difference in performance.
-<li><tt>'''csp'''.get_domain(var)</tt> <span></span>Return the list of values in the variable's
-domain.
-</li>
-<li><tt>'''csp'''.set_domain(var, domain)</tt> <span></span>Set the domain of the variable to the
-particular list of values.
-</li>
-<li><tt>'''csp'''.eliminate(var, val)</tt> <span></span>Remove the value from the variable's
-domain. <span style="background:#ff0">Note</span> that as a helpful side-effect, this function returns <code>True</code> if the value was found in the
-domain, or <code>False</code> if the value wasn't found.
-</li>
-</ul>
+----
-<ul>
+Note that the Pokemon problem is already defined for you in <tt>test_problems.py</tt>. To get a copy of it, use the method <tt>get_pokemon_problem()</tt> in <tt>lab4.py</tt>.
-<li><tt>'''csp'''.get_assigned_value(var)</tt> <span></span>If the variable has been assigned a
-value, retrieve it. Returns <code>None</code> if the variable hasn't been
-assigned yet<sup><a id="fnr.3" class="footref" href="#fn.3">3</a></sup>.
-</li>
-<li><tt>'''csp'''.set_assigned_value(var, val)</tt> <span></span>Set the assigned value of the
-variable to <tt>val</tt>, <em>returning a modified copy of the constraint satisfaction
-problem</em>. Throws an error if <tt>val</tt> is not in the domain of the
-variable, or if var has already been assigned a value. <!--- TODO ensure description up-to-date re: setting domain to [val] !-->
-</li>
-</ul>
-<ul>
-<li><tt>'''csp'''.constraints_between(var1, var2)</tt> <span></span><p>
-Return a list of all the
-constraints between var1 and var2. Arguments that are <code>None</code> will
-match anything: for example, <code>constraints_between('X',None)</code> will
-return all constraints involving <code>X</code> any any other variable, and
-<code>constraints_between(None, None)</code> will return all of the
-constraints in the problem.
-</p>
-<p>
-! 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,
- <code>csp.constraints_between(None, 'Y')</code> will return a list of all
- constraints involving 'Y' &#x2014; and the constraints will be altered
- so that 'Y' is their <i>second</i> variable (<code>var2</code>) in every case.
-</p>
-</li>
-<li><tt>'''csp'''.add_constraint(var1, var2, test_fn)</tt> <span></span><p>
-Takes two variables and a
-function to act as a constraint between them, creating a
-<code>Constraint</code> object and adding it to the list
-<code>csp.constraints</code>.
-</p>
-<p>
-The function <code>test_fn</code> must take two arguments &#x2014; a value for
-the first variable, and a value for the second variable &#x2014; and
-return <code>True</code> if the values satisfy the constraint, or <code>False</code>
-otherwise.
-</p>
-</li>
-<li><tt>'''csp'''.add_constraints(constraint_list)</tt> <span></span><p>
-Add a list of <code>Constraint</code>
-objects to the list <code>csp.constraints</code>. Useful for when you want
-to add several constraints to the problem at once, rather than
-one at a time using <code>csp.add_constraint</code>.
-</p>
-</li>
-</ul>
-<!-- TODO: I removed the copy function from the API
-<ul>
-<li><tt>'''csp'''.copy()</tt> <span></span>Return a (deep) copy of this constraint satisfaction
-problem. This method is particularly useful because
-you will want to make a copy of the <code>csp</code> every time
-you assign a value to a variable.
-</li>
-</ul>
-!-->
-</div>
-</div>
-=== Constraints ===
-<div class="outline-text-3" id="text-2-2">
-<p>
-A <code>Constraint</code> is a fairly basic object. It has three variables&#x2014;
-<code>var1</code>, <code>var2</code>, and <code>constraint_fn</code> &#x2014; and one method, <code>check(val1,
-val2)</code>.
-</p>
-<p>
-<code>const.check(val1, val2)</code> simply applies the <code>Constraint</code>'s
-constraint function to the two arguments, returning <code>True</code> if the
-values satisfy the constraint, or <code>False</code> otherwise.
-</p>
-</div>
-</div>
-<div id="outline-container-sec-2-3" class="outline-3">
-=== <span class="todo TODO">TODO</span> Worked examples ===
-</div>
-</div>
-<div id="outline-container-sec-3" class="outline-2">
+<!--=== <span class="todo TODO">TODO</span> Worked examples === -->
+<!-- todo format this section and fix footref links above
 == Footnotes: ==
 <div id="text-footnotes">
-<div class="footdef"><sup><a id="fn.1" class="footnum" href="#fnr.1">1</a></sup> <p>Naming the variables may make this easier: you have
+<div class="footdef"><sup><a id="fn.1" class="footnum" href="#fnr.1">1</a></sup> Naming the variables may make this easier: you have
 popped Alice off of the queue and are iterating over Alice's
 constraints. One of those constraints involves a neighbor, Bob. If
 Bob has a value that is incompatible with <i>all</i> of Alice's values,
-remove Bob's value and add Bob to the queue.</p></div>
+remove Bob's value and add Bob to the queue.</div>
-<div class="footdef"><sup><a id="fn.2" class="footnum" href="#fnr.2">2</a></sup> <p>Constraint
+<div class="footdef"><sup><a id="fn.2" class="footnum" href="#fnr.2">2</a></sup> Constraint
 satisfaction involves ruling out as many values as
-possible in order to limit search.</p></div>
+possible in order to limit search.</div>
-<div class="footdef"><sup><a id="fn.3" class="footnum" href="#fnr.3">3</a></sup> <p>Please note that there is a distinction between
+<div class="footdef"><sup><a id="fn.3" class="footnum" href="#fnr.3">3</a></sup> Please note that there is a distinction between
 a variable being assigned a value, and a variable having only one
 value left in its domain: a variable can have one value in its
-domain without having an assigned value yet.</p></div>
+domain without having an assigned value yet.</div>
+-->
-== Survey ==
-Please answer these questions at the bottom of your <tt>lab3.py</tt> file:
-* <tt>NAME</tt>: What is your name? (string)
-* <tt>COLLABORATORS</tt>: Other than 6.034 staff, whom did you work with on this lab? (string, or empty string if you worked alone)
-* <tt>HOW_MANY_HOURS_THIS_LAB_TOOK</tt>: Approximately how many hours did you spend on this lab? (number or string)
-* <tt>WHAT_I_FOUND_INTERESTING</tt>: Which parts of this lab, if any, did you find interesting? (string)
-* <tt>WHAT_I_FOUND_BORING</tt>: Which parts of this lab, if any, did you find boring or tedious? (string)
+== FAQ ==
-* (optional) <tt>SUGGESTIONS</tt>: What specific changes would you recommend, if any, to improve this lab for future years? (string)
+'''Q''': I am getting the right output but the wrong number of evaluations
+'''A''': Check that, when reducing domains, you are correctly considering the possibility of having multiple different constraints between two variables. (What does it mean if you have two contradictory constraints between two variables?)
-(We'd ask which parts you find confusing, but if you're confused you should really ask a TA.)
-When you're done, run the online tester to submit your code.  <!--(The online tester for Lab 3 will be made available by the weekend.)-->
+{{Survey}}