Assignment 4 Sudoku and constraint satisfaction

Artificial Intelligence Assignment 4a and 4b

The written part of this assignment (Problems 1,2, 4 worth 50 points) is due October 5 at 8 pm,
and the programming problem (Problem 3 worth 100 points) is due October 14 at 8 pm on Canvas. Download assignment4.zip from Owlspace. All written work should be placed in a file called
writeup.pdf with problem numbers clearly identified. All code should be included in submission.py
at the labeled points. For Problem 3, please run the auto grader using the command line python
grader.py and report the results in your writeup. Submit writeup.pdf for your October 5 submission. For your October 14 submission zip up submission.py as well as a new writeup.pdf.
1 Sudoku and constraint satisfaction (20 points)
The game of Sudoku consists of filling a 9x9 grid with digits 1 through 9. The 9x9 grid is divided
into nine 3x3 grids shown with the darker borders in Figure 1. Each row, each column, and each
of the nine 3x3 grids should contain each of the nine digits exactly once. A specific instance of
the Sudoku game is one in which certain digits have already been placed as in the previous figure.
The object of this exercise is to use backtracking depth-first search with forward checking and arcconsistency to solve Sudoku puzzles. Assume we formulate 9x9 Sudoku as a CSP with 81 variables,
Xij , 1 ≤ i ≤ 9, 1 ≤ j ≤ 9, where Xij denotes the grid cell at row i and column j. The domain of
each of these variables is the set {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Figure 1: An easy NYT Sudoku puzzle
1
2 • (5 points) Using the variable names above, write down all the constraints defining any partially
filled Sudoku board (not just the one in Figure 1 which is offered as an example only). You
can use constraints of the form V = v, V 6= v, as well as the AllDiff(S) constraint. V stands
for a variable and v for a value. S is a subset of variables and AllDiff takes a set of variables
S and enforces the fact that they are all distinct; it is a compact packaging of all pairwise
inequality constraints. AllDiff(V1, V2, V3) is short for {V1 6= V2, V1 6= V3, V2 6= V3}.
• (5 points) What does forward checking with an initial board do? Answer this question in
general and then illustrate your answer using the variable X74 in the board in Figure 1.
• (5 points) Variable ordering is an important part of solving CSPs in general, and Sudoku
puzzles in particular. Explain how the most-constrained variable heuristic would work in
general for Sudoku puzzles. Then, use your heuristic to determine which squares(s) will be
assigned first in the example board in Figure 1.
• (5 points) Consider variable X48 in Figure 1. Why can we assign it the value of 7? Can
forward checking and arc consistency derive this from the given constraints? Explain why or
why not.
2 Constraint satisfaction with non-binary factors (20 points)
In CSPs, a non-binary factor is a factor that involves more than two variables. For example,
consider the variables X1, X2, X3, over the domain {red, green, blue}. An example of a non-binary
factor is one that stipulates that exactly two of these three variables are assigned the value green.
CSPs with non-binary factors can be transformed into CSPs with binary factors. To do this, we
introduce a new method, one different from the one discussed in class. Here we add one auxiliary
variable A, for each non-binary factor.
• (5 points) Provide a precise definition for a transformation of this type for a k-ary factor
over the set of variables X1, . . . , Xk. For simplicity, assume that all variables have discrete,
finite domains. You may further assume that you have the extensional representation of the
factor as (X1, . . . , Xk) ∈ S where S is the the set of all k-tuples of value combinations that
are allowed. What is the domain of the new auxiliary variable created? What are the binary
factors that need to be associated with it?
• (5 points) Apply your transformation to the constraint on the variables X1, X2 and X3 over
the domain {red, blue, green} where exactly two of these variables have the value green. What
is the domain of the new auxiliary variable? Write down the definition of the new binary
factors.
• (5 points) Consider the problem of creating a crossword puzzle in which all the words must appear in some given dictionary D. We treat the dictionary as a set of words D = {w
1
, . . . , wn},
where w
i
is the i
th word. We treat each word as a sequence of letters, w
i = (w1
i
, w2
i
, . . . , wl
i
).
As an example, consider the following instance of the problem with the grid shown on the
left. Assuming the words {CAP, CAT, P IN, T EN} are in D, a possible solution for the grid
is shown on the right.
3
C A P
A
T E N
I
Formalize this instance as a CSP problem, with each variable corresponding to an empty
square in the crossword puzzle (you will need 8 variables). Write down the factors representing
the crossword constraints.
• (5 points) Note that the factors above are non-binary. If we reformulate the problem as a
binary CSP using the method from the previous parts of this problem, the auxiliary variables
and their domains have very intuitive interpretations. What are they? This answer should
not exceed two sentences!
3 Constraint solving and course scheduling (100 points)
What courses should you take in a given semester? Answering this question requires balancing your
interests, satisfying prerequisite chains, graduation requirements, availability of courses; this can be
a complex and tedious process. In this assignment, you will write a program that does automatic
course scheduling for you based on your preferences and constraints. The program will cast the
course scheduling problem as a constraint satisfaction problem (CSP) and then use backtracking
search to solve that CSP to give you your optimal course schedule.
We have already implemented a basic backtracking search for solving weighted CSPs with unary
and binary factors. First, in Problem 3.1, you will write three heuristics that will make the CSP
solver much faster. In Problem 3.2, you will add helper functions to handle more complex nonbinary factors. Finally, in Problem 3.3, you will create the course scheduling CSP and solve it using
the solver created in Problems 3.1 and 3.2.
3.1 CSP solving (40 points)
We will be working with weighted CSPs, which associate a weight with each assignment x based
on the product of m potential functions or factors.
weight(x) = Ym
j=1
fj (x)
where each potential fj (x) ≥ 0. For unweighted CSPs, fj (x) ∈ {0, 1}. Our goal is to find the
assignment(s) with the highest weight. In this problem, we will assume that each potential is either
a unary potential (depends on exactly one variable) or a binary potential (depends on exactly two
variables). We will refer to potentials and factors interchangeably.
Backtracking search operates over partial assignments and associates a weight with each partial
assignment, which is the product of all the potentials that depend only on the assigned variables
in x. When we assign a value to a new variable Xi
, we multiply in all the potentials that depend
4 only on Xi and the previously assigned variables. The function get delta weight() returns the
contribution of these new potentials based on the unary potentials and binary potentials in the
CSP. An important case is when get delta weight() returns 0. In this case, the weight of any
full assignment that extends the new partial assignment will also be zero, so there is no need to
search further from that new partial assignment.
We have implemented a basic backtracking solver for you. You can try it out in a Python shell on
the simple Australia map coloring problem (this is also provided in run p1.py):
import util, submission
csp = util.create_map_coloring_csp()
alg = submission.BacktrackingSearch()
alg.solve(csp)
print alg.optimalAssignment
Look at the function BacktrackingSearch.reset results() in submission.py to see the other
fields which are set as a result of solving the weighted CSP. You should read util.CSP and
submission.BacktrackingSearch carefully to make sure that you understand how the backtracking search works on this CSP.
• (5 points) Let’s create a CSP to solve the n-queens problem: Given an n×n board, we would
like to place n queens on this board such that no two queens are on the same row, column,
or diagonal. Implement create nqueens csp() by adding variables and some number of
binary potentials. You can refer to the CSP examples we provided in util.py for guidance.
You can also run the examples with run p1.py. Note that the solver collects some basic
statistics on the performance of the algorithm. You should take advantage of these statistics
for debugging and analysis. You should get 92 (optimal) assignments for with exactly 2057
operations (number of calls to backtrack()). Hint: If you get a larger number of operations,
make sure your CSP is minimal.
• (10 points) You might notice that our search algorithm explores quite a large number of
states even for the 8×8 board. Let us see if we can do better. One variable-ordering heuristic
to consider is the most constrained variable (MCV). To choose an unassigned variable, pick
the Xj that has the fewest number of values v which are consistent with the current partial
assignment (get delta weight on Xj = v returns a non-zero value). Implement this heuristic
in get unassigned variable() under the condition self.mcv = True. You should observe
a non-trivial reduction in the number of states explored.
• (10 points) A heuristic for ordering values of a variable’s domain is the least constraining value
(LCV). Given the next variable to be assigned Xj , sort its domain values a in descending
order of the number of values b of an unassigned variable Xk that are consistent with it
(consistent means the binary potential on Xj = a and Xk = b is non-zero). Note that you
should only count values of b which are already consistent with the existing partial assignment.
Implement this heuristic in get ordered values() under the condition self.lcv = True.
You will need to use binaryPotentials in CSP.
• (15 points) So far, our heuristics have only looked at the local effects of a variable or value.
Let us now implement arc consistency (AC-3). After we set variable Xj to value a, we
5 remove the values b of all neighboring variables Xk that could cause arc-inconsistencies. If
Xk’s domain has changed, we use Xk’s domain to remove values from the domains of its
neighboring variables. This is repeated until no domains have changed. This domain pruning
could significantly reduce the branching factor of backtracking search, although at some cost.
Please fill in arc consistency check() and backtrack() to complete the implementation
of arc consistency. You might find copy.deepcopy() on self.domains useful. You should
make sure that your existing MCV and LCV implementation are compatible with your AC-3
algorithm as we will be using all three heuristics together during grading. You should observe
a very significant reduction in the number of steps taken to reach the first full assignment.
3.2 Handling n-ary potentials (10 points)
So far, our CSPs only handle unary and binary potentials, but for course scheduling, we need
potentials that involve more than two variables. In this problem, you will take one type of n-ary
constraints and reduce them to a set of binary potentials with auxiliary variables, as discussed in
class.
• (10 points) Implement get sum variable(), which takes in a list of non-negative integervalued variables and returns a variable whose value is constrained to be equal to the sum of
the variables. You will need the domains of the variables passed in, which you can assume
contain only non-negative integers. Use the technique of adding auxiliary variables discussed
in class.
3.3 Course scheduling (50 points)
In this problem, we will apply your weighted CSP solver to the problem of course scheduling.
We have scraped a subset of courses that are offered in our department. For each course in this
dataset, we have information on which semesters it is offered, the prerequisites (which may not be
fully accurate due to ambiguity in the listing), and the range of credits allowed. You can take a
look at all the courses in rice cs courses.json. Please read util.py, paying particular attention
to util.Course and util.CourseBulletin to understand how this information is parsed.
To specify a desired course plan, you would need to provide a profile which specifies your constraints
and preferences for courses. A profile is specified in a text file (see profile*.txt for examples). The
profile file has four sections. The first section specifies a fixed minimum and maximum (inclusive)
number of credits you need to take for each semester. In the second section, you register for the
semester that you want to take your courses in. For example, register Fall2014 would sign you
up for this semester. The semesters need not to be contiguous, but they must follow the exact
format FallNNNN or SprNNNN. The third section specifies the list of courses that you have taken
in the past using the taken keyword. The last section is a list of courses that you would like to
take during the registered semesters, specified using request. Not every course listed in request
must appear in the generated schedule. Conversely, a list of requests could potentially result in an
infeasible schedule due to the additional constraints we will discuss next.
Note: there’s no space between items separated by commas.
6 If you want to take a course in one of a specified set of semesters, use the in modifier. For example,
if you want to take COMP310 in either Fall2013 or Fall2014, do:
request COMP310 in Fall2013,Fall2014
Another operator you can apply is after, which specifies that a course must be taken after another
one. For example, if you want to choose COMP215 and take it after both COMP140 and COMP182,
add:
request COMP215 after COMP140,COMP182
Note that this implies that if you take COMP215, then you must take or have taken both COMP140
and COMP182. In this case, we say that COMP140 and COMP182 are prereqs of this request.
If you request course A after B, and B is a prerequisite of A (based on CourseBulletin), we will
automatically add B to the variables. But be careful that they are NOT added to the request data
structure. So, in some questions below, you may need to loop over all variables added in the csp
rather than courses in requests.
Finally, the last operator you can add is weight, which adds non-negative weight to each request.
All requests have a default weight value of 1. Requests with higher weight should be preferred by
your CSP solver.
Note that you can write multiple requests of courses in to one line such as:
request COMP215,COMP310,COMP410
But if there are constraints in that request, the constraints apply to all courses requested.
request COMP215,COMP310 in Fall2014,Fall2015 after COMP182 weight 5
It means that both COMP215 and COMP310 should be taken in Fall2014 or Fall2015, the have the
same prerequisite COMP182 and they are all weighted 5. It is important to note that the request of
a certain course may not be satisfied, but if it is, the constraints specified by the various operators
after, in must be satisfied.
We have done all the parsing of the course catalog and course profile for you, so all you need
to work with is the collection of Request objects in Profile and CourseBulletin to know when
courses are offered and the number of units of courses. Your task is to take a profile and bulletin and
construct a CSP. We have started you off with code in SchedulingCSPConstructor that constructs
the core variables of the CSP as well as a basic constraint. The variables are requested courses (as
mentioned above, untaken prereqs have been added to the variables automatically), and the value
of such a variable is one of the semesters registered in this profile file or None, which indicates that
that course will not be taken in any semester. We will add auxiliary variables to handle non-binary
factors later. We have also implemented some basic constraints: add bulletin constraints(),
which enforces that a course can only be taken if it is offered in that semester (according to the
bulletin).
• (10 points) Implement the function add semester constraints(). This is when your profile
specifies which semester(s) you want your requested courses to be taken in. This is not saying
7 that one of the courses must be taken, but if it is, then it must be taken in one of the specified
semesters. We have written a verify schedule() function in grader.py that determines if
your schedule satisfies all of the given constraints. Note that since we are not dealing with
credits yet, it will print None for the number of credits of each course.
• (10 points) Now you will add the weights to your requests in add request weights(). By
default, all requests have a weight of 1 regardless of whether it is satisfied or not. When
a weight is explicitly specified, it should only contribute to the final weight if one of the
requested courses is assigned a semester i.e. is not None. NOTE: Each grader test only tests
the function you are asked to implement. To test your CSP with multiple constraints you
can use run p3.py and change the constraints that you want to add.
• (10 points) Implement the add prereq constraints() function. You must make sure that if
a course is taken in a certain semester, its prerequisites must all be taken before that semester.
You should write your own function that checks the values (i.e. semesters) of the course you
request and its prerequisites and make sure that the values of prerequisites are smaller than
that of the course you request if not None.
• (10 points) Now you will add the credit constraints in add credit constraints(). You
must ensure that the sum of credits per semester for your schedule are within the min and
max threshold (inclusive). You should use get sum variable() here . In order for our
solution extractor to obtain the number of credits, for every course, you must add a variable
(courseId, semester) to the CSP taking on a value equal to the number of units being taken
for that course during that semester. When the course is not taken during that semester, the
credits should be 0. Some courses have variable credit units. For example, a course can be
taken as a 3 credit course or 4 credit course. You solution should be able to assign the correct
unit so that the requirement of sum of credits for a semester is met.
• (10 points) Now try to use the course scheduler for Spring 2017 (the next semester). Create
your own profile.txt and then run the course scheduler:
python run_p3.py profile.txt
You might want to turn on the appropriate heuristic flags to speed up the computation. Does
it produce a reasonable course schedule? Please submit your profile.txt; and include the
schedule that your solver designed for you in writeup.pdf.
4 Sudoku and repair algorithms (10 points)
(Problem 6.15 in textbook) We introduced Sudoku as a CSP to be solved by a constructive algorithm
such as a depth-first backtracking search augmented by forward-checking and arc-consistency. It
is possible to solve Sudoku using a repair algorithm. How well would a local solver using the minconflicts heuristic do on Sudoku problems? Would you recommend a repair-based or a constructive
approach for solving Sudoku? Explain your choice.