HW 1 -- CSP & Graphical Models

The questions below are due on Tuesday February 18, 2025; 11:59:00 PM.

You are not logged in.
Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.

This week's Colab notebook can be found here: Colab Notebook (Click Me!)

1) Class scheduling§

Let's look at the formulation of a class scheduling problem in which we try to pick courses for 4 years at MIT. We're going to say that there are four "slots" each term, and each will be assigned to one course. So, there are 32 variables and the domain of each variable is the set of all courses. A complete assignment to the variables is a class schedule.

Let's make a couple of assumptions:

Assume that you will take exactly 4 courses each term.
Assume that pre-requisites are a list of courses that must all be taken in previous terms. So, there are no "or" choices or co-requisites.

The term slots are written as, e.g. (Fall, 1, 1) (Fall, 1, 2) ... (Spring, 4, 4), starting with the slots for the fall term of the first year and going through the slots for the spring term of the fourth year. So (Fall, 1, 2) refers to the second slot of the fall term of the first year.

Indicate which of the following statements best describe the constraints required in this formulation. This means that you might mark some statements as false that are really, strictly speaking, true simply because there is a better choice on the list.

	A constraint between each pair of variables representing term slots for a given term, e.g. (Fall, 1, 1) (Fall, 1, 2) etc., which checks that the classes assigned to those slots do not have conflicting times.
	A constraint between each pair of variables representing term slots for a given term, e.g. (Fall, 1, 1) (Fall, 1, 2) etc., which checks that the number of courses taken that term is no more than four.
	A constraint between every pair of variables representing term slots for a given term, that ensures that the same course is not scheduled to be taken more than once.
	A constraint between every pair of variables representing all the term slots that ensures that the same course is not scheduled to be taken more than once.
	The domain of each variable is limited to the courses offered that term.
	The domain of each variable is limited to those courses with non-conflicting times.
	A constraint between every pair of variables that checks that if the course assigned to one variable is a pre-requisite of the other, then the pre-requisite course is scheduled in the earlier term.
	A constraint between every pair of variables in different terms that checks that if the course assigned to one variable is a pre-requisite of the other, then the pre-requisite course is scheduled in the earlier term.

2) Map coloring§

Let's look at a simple map coloring problem and explore the behavior of constraint propagation (AC-3), backtracking and forward checking in this context. Here is the constraint graph of the CSP:

Map-coloring Image

The letters indicate the initial domain of each variable. Each edge in the graph represents a constraint that the two variables it connects must have different colors.

2.1) Arc consistency§

Enter the values in each of the indicated variable domains after any changes required to achieve arc consistency for just that arc. Then, assume that the following arcs are done sequentially, with the effects on the domains propagating to the next question.

Below we give you a sequence of six arcs, each defined by a pair of variables, e.g. V_1 - V_2. For each arc, you should enter the domains D_1 and D_2 after dropping any entries necessary to achieve arc consistency on that arc.

V_1 - V_2

D_1 =

D_2 =
V_1 - V_3

D_1 =

D_3 =
V_2 - V_4

D_2 =

D_4 =
V_3 - V_4

D_3 =

D_4 =
V_1 - V_2

D_1 =

D_2 =
V_1 - V_3

D_1 =

D_3 =

2.2) Backtracking§

Assume we use pure backtracking to search for a solution to this problem.

We use a fixed variable ordering in the search (V_1, V_2, V_3, V_4)
The values are considered in the order shown in the picture above.

Show the order in which assignments for each variable are considered by backtracking (this is analogous to the order in which nodes are expanded by depth-first search). Show the variable assignment even if it is immediately found to be inconsistent upon testing. Assume that the search continues even after finding a valid solution.

Show a total of 10 variable assignments. We have split them into 3 segments so that you can check your partial answers.

We start by assigning variables to the first available value. Enter a Python list of these first 4 assignments. Each assignment is a string consisting of a number from 1 to 4 (indicating the variable) followed by a letter, drawn from 'R', 'G', 'B', e.g. '1R'.

We backtrack to fix the conflict between V3 and V4. Enter a Python list of the next 2 assignments that fixes this. Each assignment is a string consisting of a number from 1 to 4 (indicating the variable) followed by a letter, drawn from 'R', 'G', 'B', e.g. '1R'.

Enter a Python list of the next 4 assignments. Each assignment is a string consisting of a number from 1 to 4 (indicating the variable) followed by a letter, drawn from 'R', 'G', 'B', e.g. '1R'.

2.3) Backtracking with forward-checking§

Repeat assuming we use backtracking with forward checking to search for a solution to this problem. We use the same variable ordering and value ordering as before. Show the order in which assignments are considered by BT-FC. Whenever propagating after an assignment causes a domain to become empty, that causes backup in the search. Assume that the search continues even after finding a valid solution.

Show a total of 10 assignments. We have split them into three segments so that you can check your partial answers.

We start by assigning V1 and V2 and correcting V2 with forward checking. Enter a Python list of the first 3 assignments that shows this. Each assignment is a string of a number from 1 to 4 (indicating the variable) followed by a letter, drawn from 'R', 'G', 'B', e.g. '1R'.

We eventually find a satisfying assignment for all variables. Enter a Python list of the next 3 assignments that shows this. Each assignment is a string of a number from 1 to 4 (indicating the variable) followed by a letter, drawn from 'R', 'G', 'B', e.g. '1R'.

Finally, we backtrack, assign a new value for V1, and continue. Enter a Python list of the next 4 assignments. Each assignment is a string of a number from 1 to 4 (indicating the variable) followed by a letter, drawn from 'R', 'G', 'B', e.g. '1R'.

3) Local search§

3.1) §

When there is some kind of information available about the “quality” of a non-satisfying assignment, then we can do local search, trying to improve that solution by making a sequence of small improving changes.

Which of the following might make good measures of the quality of an assignment, which would decrease as the assignment improved toward a solution?

	Number of violated constraints
	Sum of the “amount” each constraint is violated (for example, how much two objects interpenetrate, given a collision-free constraint)
	Number of values in the domains of the variables involved in violated constraints

3.2) §

Consider an algorithm in which you iterate these steps until you find a solution:

Find a violated constraint.
Make a minimal reassignment of values to variables involved in it, so that it becomes satisfied.

Is it guaranteed to find a satisfying assignment if one exists?

	True
	False

3.3) §

Consider an algorithm in which you iterate these steps until you find a solution:

Pick a variable at random and a possible assignment to it.
If changing that variable to have that value decreases the number of constraints that are violated, make the change, otherwise do not.

Is it guaranteed to find a satisfying assignment if one exists?

	True
	False

3.4) §

Consider an algorithm in which you iterate these steps until you find a solution:

Pick a variable at random and a possible assignment to it.
If changing that variable to have that value improves the quality of the assignment, make the change.
Otherwise, with probability e^{-\delta / T} where \delta is the change in assignment quality, accept the change

Is there a way to manage the T parameter so this is guaranteed to find a satisfying assignment if one exists?

	True
	False

4) CSP Coding§

4.1) CSP Warmup§

Create a BinaryCSP with the criteria described in the docstring.

For reference, our solution is 4 lines of code.

4.2) Backtracking Search§

Complete this implementation of backtracking search for binary CSPs.

Use the provided implementation of AC-3 (reduce_csp_ac3) after you have made each assignment.
Use order_variable_values which implements the least-constraining-value heuristic.
Use select_unassigned_variable which implements the MRV (minimum-remaining values) heuristic. This chooses the next variable to assign by the fewest possible valid values.

For reference, our solution is 31 lines of code.

4.3) Sudoku Solving§

Use your implementation of backtracking search to solve sudoku puzzles like the following. The rules of sudoku can be found here.

sudoku_puzzle = [
  [0, 0, 3, 0, 2, 0, 6, 0, 0],
  [9, 0, 0, 3, 0, 5, 0, 0, 1],
  [0, 0, 1, 8, 0, 6, 4, 0, 0],
  [0, 0, 8, 1, 0, 2, 9, 0, 0],
  [7, 0, 0, 0, 0, 0, 0, 0, 8],
  [0, 0, 6, 7, 0, 8, 2, 0, 0],
  [0, 0, 2, 6, 0, 9, 5, 0, 0],
  [8, 0, 0, 2, 0, 3, 0, 0, 9],
  [0, 0, 5, 0, 1, 0, 3, 0, 0],
]

For reference, our solution is 61 lines of code.

In addition to all of the utilities defined at the top of the colab notebook, the following functions are available in this question environment: run_backtracking_search. You may not need to use all of them.

def solve_sudoku_puzzle(puzzle):
  '''Fill in all zeros in a partially filled sudoku puzzle.

Args:
    puzzle: A list of lists of ints. Zero means empty.

Returns:
    finished_puzzle: A list of lists of ints with no empties.
  '''
  csp = create_sudoku_csp(puzzle)
  solution = run_backtracking_search(csp)
  return solution_to_sudoku_grid(solution)

def solution_to_sudoku_grid(solution):
  rows = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
  cols = list(range(1, 10))
  grid = [[None for _ in cols] for _ in rows]
  for variable, value in solution.items():
    r, sc = variable.name.split("_")
    grid[rows.index(r)][cols.index(int(sc))] = value
  return grid

def create_sudoku_csp(puzzle):
  assert len(puzzle) == 9
  assert len(puzzle[0]) == 9
  rows = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
  cols = list(range(1, 10))
  variables = {}  # (r, c) -> CSPVariable
  for r in rows:
    for c in cols:
      v = CSPVariable(f"{r}_{c}", set(range(1, 10)))
      variables[(r, c)] = v
  constraints = set()
  neq = lambda x, y: x != y
  # Generic sudoku constraints
  for r in rows:
    for i, c1 in enumerate(cols[:-1]):
      for c2 in cols[i+1:]:
        constraints.add(ImplicitBinaryConstraint(
          variables[(r, c1)],
          variables[(r, c2)],
          neq))
        
  # TODO: column constraint
  # TODO: box constraint

# Constraints from puzzle
  for i, r in enumerate(rows):
    for j, c in enumerate(cols):
      if puzzle[i][j] > 0:
        constraints.add(ExplicitBinaryConstraint(
          variables[(r, c)],
          variables[(r, c)],
          {(puzzle[i][j], puzzle[i][j])},
        ))
  return BinaryCSP(set(variables.values()), constraints)

4.4) AC3 and me§

Rerun the solver with and without AC3.

How long did it take the solver to terminate with AC3 enabled?

Select one:

1 second

Less than a minute

More than five minutes
How long did it take the solver to terminate without AC3 enabled?

Select one:

1 second

Less than a minute

More than five minutes

5) Bayes Nets and Tables§

Let's first look at how to go back and forth between Bayes nets and probability tables. Consider the following simple Bayes net, with three variables, A, N and S. Note that we have only given the values for where the dependent variable is true.

How many rows are there in the probability table over the joint distribution of A, N, and S?

Enter an integer.
What is the probability that the airspeed is low (A=T), the nose is up (N=T) and the aircraft is not in stall (S = F)?

Enter a number that is accurate to within 1.0e-5. You can also enter a python expression that will evaluate to a number (e.g., 3*2 + 4 - 7/11.0).
What is the probability that the aircraft is in stall (S = T), given that we don't know the air speed or the nose angle?

Enter a number that is accurate to within 1.0e-5. You can also enter a python expression that will evaluate to a number (e.g., 3*2 + 4 - 7/11.0).

6) Satellites§

We realized there was previsouly a bug in the problem. We have since replaced the problem with simply "click for free points". (👏 Everyone let's thank the anonymous student who raised the question 😉)

Click for a 1 pt

Click Submit for a 1 pt
Click for another pt

Click Submit for a 1 pt
Yet another one!

Click Submit for a 1 pt
Life doesn't keep giving us free points... Last one...

Click Submit for a 1 pt

7) Feedback§

How many hours did you spend on this homework?
Do you have any comments or suggestions (about the problems or the class)?

	1 second
	Less than a minute
	More than five minutes

	1 second
	Less than a minute
	More than five minutes