ASSIGNMENT 3

The goal of this assignment is to give you practice solving constraint satisfaction problems (CSPs). There are two problems in this assignment. The first one is easier, and worth 10 points, the second one worth 40 points. If you search the internet, you may find solutions of various sorts to the problems, but what I want is for you to show me your work at each step and explain what you did, in terms of CSP methods so that I know you understand CSPs and their solution.

As you work through these problems, tell me whether you are using forward checking, backtracking, constraint propagation, the heuristics of most constrained variable (minimum remaining values), or least constraining value. Were you able to do anything with the structure of the problems, or were you able to use a local search method like min-conflicts?

Problem 1:
Consider the constraint graph shown below. The domain for every variable is {1, 2, 3, 4}.

There are two unary constraints:

1) Variable "a" cannot be assigned the values 3 or 4.

2) Variable "b" cannot be assigned the value 4.

There are eight binary constraints stating that the variable connected by an edge cannot have the same value.

Work through the problem and find a solution that does not violate the constraints. Is there one solution, more than one solution, or no solution? If you found a solution, what was it?

As you work through the problem, write out what CSP technique you are using to get to a certain point. Show all of your work (neatly) so that I can follow your approach.

Problem 2:
We saw an example of a cryptarithmetic problem in the slides in class. This is a different one. Solve the problem using whatever technique(s) you find appropriate, and document exactly what you did at what step.

  S E N D
+ M O R E
----------
M O N E Y

Recall that each letter represents a different digit, so each letter must have a different value than the other digits. There may also be carry variables as a result of the addition in each column. A carry variable can only take on the values of {0, 1} and are definitely not unique. In this particular problem, you might start with equations for each of the columns like:

  D + E = Y + x1*10
  N + R + x1 = E + x2*10
  ... and so on ...

Were you able to find a solution? Is there one solution, several solutions, or no solution? If you found a solution, what was it?

Again, as you work through the problem, write out what CSP you are using to get to a certain point. Show all of your work (again neatly) so that I can follow your approach.

Page last updated: August 17, 2018