Description
1 Introduction
In this project, you will implement some new constraints and backtracking search algorithms.
Note that this code base is unrelated to the Berkeley pacman code base. So you will not need any of the
files from A1 nor A2. (We know Pacman is loved by many of you. It will make a glorious comeback in A4.)
The code for this project contains the following files, available as a zip archive.
Files you’ll edit:
backtracking.py Where all of the code related to backtracking search is located. You will
implement forward checking and gac search in this file.
csp_problems.py Where all of the code related implementing different CSP problems is located.
You will implement a new version of the nQueens CSP and a CSP to solve the
sport tournament scheduling problem in this file.
constraints.py Where all of the code related implementing various constraints is located. You
will implement a new summation constraint in this file.
Files you can ignore:
csp.py File containing the definitions of Variables, Constraints, and CSP classes.
util.py Some basic utility functions.
nqueens.py Solve nQueens problems.
sudoku.py Solve sudoku problems.
autograder.py Program for evaluating your solutions. As always your solution might also be
evaluated with additional tests besides those performed by the autograder.
Files to Edit and Submit: You will fill in portions of backtraking.py, csp.py, and csp_problems.py
during the assignment. You may also add other functions and code to these file so as to create a modular
implementation. You will submit these file with your modifications. Please do not change the other files in
this distribution.
Evaluation: Your code will be autograded for technical correctness. The tests in autograder.py will be
run as well as some additional tests. Please do not change the names of any provided functions or classes
within the code, or you will wreak havoc on the autograder.
Getting Help: You are not alone! If you find yourself stuck on something, contact us for help. The
piazza discussion forum will be monitored and questions answered, and you can also ask questions about the
assignment during office hours. If you can’t make our office hours, let us know and we will arrange a different
appointment. We want the assignment to be rewarding and instructional, not frustrating and demoralizing.
But, we don’t know when or how to help unless you ask.
Piazza Discussion: Please be careful not to post spoilers.
What to Submit
You will be using MarkUs to submit your assignment. MarkUs accounts for the course will be soon be set
up. You will submit four files:
Your modified backtracking.py
Your modified csp_problems.py
Your modified constraints.py
A signed copy of the following acknowledgment
1
Note: In the various parts below we ask a number of questions. You do not have to hand in answers to these
questions, rather these questions are designed to help you understand what is going on with search.
Autograder
autograder.py is not the same as the Berkeley autograder. You can only run the command
python autograder.py -q qn
where qn is one of q1, q2, q3, q4, or q5. Or you can run the grader on all questions together with the
command
python autograder.py
Question 1 (4 points): Implementing a Table Constraint
backtracking.py already contains an implementation of BT (plain backtracking search) while csp_problems.py
contains an implementation of the nQueens problem. Try running
python nqueens.py 8
to solve the 8 queens problem using BT. If you run
python nqueens.py -c 8
the program will find all solutions to the 8-Queens problem. Try
python nqueens.py –help
to see the other arguments you can use. (However, you haven’t implemented FC nor GAC yet, so you can’t
use these algorithms yet.) Try some different small numbers with the ’-c’ option, to see how the number of
solutions grows with the number of Queens. Also observe that even numbered queens are generally faster
to solve, and the time to find a single solution for ’BT’ grows quite quickly. Observe the number of nodes
explored. Later once you have FC and GAC implemented you will see that they explore fewer nodes.
For this question look at constraint.py. There you will find the class QueensTableConstraint that you
have to implement for this question. This class creates a table constraint to capture the nQueens constraint.
Once you have that implemented you can run
python nqueens.py -t 8
to solve the nQueens CSP using your table constraint implementation. Check a number of sizes and ’-c’
options: you should get the same solutions returned irrespective of whether or not you use ’-t’. That is, your
table constraint should yield the same behavior as the original QueensConstraint.
Question 2 (5 points): Forward Checking
In backtracking.py you will find the unfinished function FC. You have to complete this function. Note that
the essential subroutine FCCheck has already been implemented for you. Note that your implementation
must deal correctly with finding one or all solutions. Check how this is done in the already implemented BT
algorithm … just be sure that you restore all pruned values even if FC is terminating after one solution.
After implementing FC you will be able to run
2
python nqueens.py -a FC 8
to solve 8-Queens with forward checking. Solve some different sizes and check how the number of nodes
explored differs from when BT is used.
Also try solving sudoku using the command
python sudoku.py 1
Which will solve board #1 using Forward Checking. Try other boards (1 to 7). Also try
python sudoku.py -a ’BT’ 1
to see how BT performs compared to FC. Finally try
python sudoku.py -a ’FC’ -c 1
To find all solutions using FC. Check if any of the boards 1-7 have more than one solution.
Question 3 (7 points): GAC Enforce and GAC
In backtracking.py you will find unfinished GacEnforce and GAC routines. Complete these functions.
After finishing these routines you will be able to run
python nqueens.py -a GAC 8
Try different numbers of Queens and see how the number of nodes explored differs from when you run FC.
Does GAC also take less time than FC on sudoku? What about on nqueens?
Now try running
python sudoku.py -e 1
which will not do any backtracking search, it will only run GacEnforce.
Try running only GacEnforce on each board to see which ones are solved by only doing GacEnforce.
Question 4 (2 points): AllDiff for Sudoku
In csp_problems.py you will find the function sudokuCSP. This function takes a model parameter that is
either ’neq’ or ’alldiff’. When model == ’neq’ the returned CSP contains many binary not-equals
constraints. But when model == ’alldiff’ the model should contain 27 allDifferent constraints.
Complete the implementation of sudokuCSP so it properly handles the case when model == ’alldiff’ using
allDifferent constraints instead of binary not-equals.
Note that this question is very easy as you can use the class AllDiffConstraint(Constraint) that is
already implemented in constraints.py. However, you must successfully complete Question 3 to get any
marks on this question.
Question 5 (4 points): NValues Constraint
The NValues Constraint is a constraint over a set of variables that places a lower and an upper bound on
the number of those variables taking on a specified value. In constraints.py you will find an incomplete
implementation of class NValuesConstraint. In particular, the function hasSupport has not yet been
implemented. Complete this implementation.
3
Working successfully in a pair
You may work in pairs for this assignment.
If you are working with a partner, make sure that you are actually working together. Your goal should be for
the two of you to help each other learn the material and to avoid getting stuck with frustrating errors. If you
split up the assignment and work separately, you are not getting practice on all aspects of the assignment.
Sometimes a student who is working with a partner drops the course or becomes ill in the middle of an
assignment. If this happens, the other partner is still responsible for completing the assignment on time. If
he or she has been actively engaged in the entire assignment, this should not be a problem; the assignments
are designed so that an individual student can complete them. However, if the remaining partner has not
been actively involved or does not have copies of all of the work, they will have serious difficulty completing
the assignment. Make sure you don’t find yourself in this situation: Be active in all parts of the assignment,
and make sure that at the end of each meeting, both partners have a copy of all of the work.
4
