Lab 3: Constraint Satisfaction

From 6.034 Wiki

This lab is due by Wednesday, October 11 at 10:00pm.

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/lab4

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

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

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

All of your answers belong in the main file lab4.py. To submit your lab to the test server, you will need to download your key.py file and put it in either your lab4 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 be assigned
• value: something that can be an assignment
• domain: a set of values
• constraint: a condition that limits domains of possible values

Part 1: Warm-up

Your first major task will be to write a constraint solver that uses depth-first search to find a solution to a constraint satisfaction problem. First, however, you will write two helper functions which you may want to use later on.

• 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; or None if there is no solution to the problem
• num_extensions is the number of extensions performed during the search

Here is a rough outline of how to proceed:

1. Initialize your agenda and the extension count.
2. Until the agenda is empty, pop the first problem off the list and increment the extension count.
3. If any variable's domain is empty or if any constraints are violated, the problem is unsolvable with the current assignments.
4. If none of the constraints have been violated, check whether the problem has any unassigned variables. If not, you've found a complete solution!
5. 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.
6. 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. 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 to find inconsistencies before it's too late

Forward checking is a strategy for eliminating impossible values in advance to cut down on the amount of search we have to do.

Finding inconsistent values in neighbors

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

For a given neighbor n of a variable v, if n has a value nval that violates a constraint with every value in v's domain, then nval is inconsistent with n and v and should be removed from n's domain.

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. 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.

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, checks if there are any constraint violations between two particular variable assignments.

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 making each assignment.

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!

Domain reduction

Forward checking is a powerful tool for checking ahead for inconsistencies and reducing the search space. However, we can make it even more powerful by utilizing propagation. Currently, when we check neighbors for inconsistencies, we check a particular variable's neighbors and then terminate. With propagation, however, we repeatedly forward check as more inconsistencies are found, causing a chain reaction of searches through our assignment-space.

An important thing to consider is that there are actually two different use cases for propagation!

• We can use propagation with forward checking while making assignments; this allows us to look far ahead and remove inconsistencies before the search algorithm encounters them.
• We can use propagation in an algorithm called domain reduction. Domain reduction is applied to a CSP before search even begins, allowing us to prune the domains of variables in the CSP before the solver attempts to solve it.

As it turns out, the implementation for both of these are effectively identical. As such, we will (for now) lump them together into a function called domain_reduction.

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) :

Here is a rough description outline of the algorithm:

1. Establish a queue if it's not supplied by the caller. (Hint: csp.get_all_variables() will make a copy of the variables list.)
2. Until the queue is empty, pop the first variable var off the queue.
3. 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).
4. If any variable has an empty domain, quit immediately and return None.
5. 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.

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!

Propagation through reduced domains

We will once again update our CSP solver so that it can take advantage of domain reduction. 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.

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.

Answer the following questions in your lab4.py file:

Question 3

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.)

Question 4

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 answers (as integers) in for ANSWER_3 and 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 results in 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 singleton domains, and propagation through all reduced 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 which is the test that variables must pass in order to be added to the 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, the three enqueueing conditions we've seen are:

1. forward checking: never adds a variable to the queue
2. propagation through singleton domains: adds a variable to the queue if its domain has exactly one value in it
3. domain reduction / propagation through reduced domains: adds a 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, don't use any 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

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

def constraint_equal(a,b) :
   return a == b

def constraint_different(a,b) :
   return a != b

pokemon_problem = ConstraintSatisfactionProblem(["Q1","Q2","Q3","Q4","Q5"])

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"])

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)

# 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"])