Assignment #3: CSP solution

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 les 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 les, 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 le.




csp_problems.py Where all of the code related implementing di erent 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 le.




constraints.py Where all of the code related implementing various constraints is located. You will implement a new summation constraint in this le.




Files you can ignore:




csp.py File containing the de nitions 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 ll in portions of backtraking.py, csp.py, and csp_problems.py during the assignment. You may also add other functions and code to these le so as to create a modular implementation. You will submit these le with your modi cations. Please do not change the other les 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 nd 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 o ce hours. If you can't make our o ce hours, let us know and we will arrange a di erent 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 les:




Your modi ed backtracking.py




Your modi ed csp_problems.py




Your modi ed 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 nd 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 di erent 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 nd 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 nd 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 nd the un nished 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 nding 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 di erent sizes and check how the number of nodes explored di ers 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 nd 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 nd un nished GacEnforce and GAC routines. Complete these functions. After nishing these routines you will be able to run




python nqueens.py -a GAC 8




Try di erent numbers of Queens and see how the number of nodes explored di ers 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): AllDi for Sudoku




In csp_problems.py you will nd 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 speci ed value. In constraints.py you will nd 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 di culty completing the assignment. Make sure you don't nd 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.