Solved–Homework Assignment 3: Constraint Satisfaction– Solution

Description

Evaluation Details

Your code will be autograded for technical correctness. The tests in autograder.py will be run. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. If your code fails all of the tests performed by the script (using Python version 3.7), you will receive zero marks. It’s up to you to create test cases to further test your code—that’s part of the assignment!

When your code is submitted, we will run a more extensive set of tests. You have to pass all of these more elaborate tests to obtain full marks on the assignment.

Your code will not be evaluated for partial correctness, it either works or it doesn’t. It is your responsibility to hand in something that passes at least some of the tests in the provided testing script.

Make certain that your code runs on teach.cs using Python3 (version 3.7) using only standard im-ports. This version is installed as “python3” on teach.cs. Your code will be tested using this version and you will receive zero marks if it does not run using this version.

Do not add any non-standard imports from within the Python file you submit (the imports that are already in the template files must remain). Once again, non-standard imports will cause your code to fail the testing and you will receive zero marks.

Do not change the supplied starter code. Your code will be tested using the original starter code, and if it relies on changes you made to the starter code, you will receive zero marks.

Introduction

There are six questions in this assignment. Two problems will ask you to implement two constraint propagators—a Forward Checking constraint propagator, and a Generalized Arc Consistence (GAC) con-straint propagator. Three problems will ask you to encode constraints. The final problem will ask you to encode a CSP using some of your encoded constraints.

What is supplied

Files you will modify:

backtracking.py. Where all of the code related to backtracking search is located. You will imple-ment forward checking and GAC search in this file.

csp problems.py. Where all of the code related to implementing different CSP problems is located. You will implement a new version of the nQueens CSP and a CSP to solve the class scheduling problem in this file.

constraints.py. Where all of the code related implementing various constraints is located. You will implement an NValues 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. Solves nQueens problems.

class scheduling.py. Solves class scheduling 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.

Question 1: Implementing a Table Constraint (worth 10/100 marks)

The file backtracking.py already contains an implementation of BT (plain backtracking search) while csp problems.py contains an implementation of the nQueens problem. Try running:

python3 nqueens.py 8

to solve the 8 queens problem using BT. If you run:

python3 nqueens.py -c 8

the program will find all solutions to the 8-Queens problem. Try:

python3 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 constraints.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. This table constraint will explicitly store sets of all satisfying tuples of values that can be assigned to the variables. Once you have implemented QueensTableConstraint you can run:

python3 nqueens.py -m “table” 8

to solve the nQueens CSP using your table constraint implementation.

For nQueens problem, if ’-c’ is provided, then all solutions will be generated. It generates only one solu-tion by default. The ’-m’ option specifies which constraint setting to use (row, table, alldiff). We can also change the algorithm used by providing ’-a’ option (BT, FC, GAC). Check a number of sizes using the ’-c’ option: you should get the same solutions returned irrespective of whether or not you use the ’-m’ option. That is, your table constraint should yield the same behavior as the original QueensConstraint.
Assignment 3, University of Toronto, CSC384 – Intro to AI, Winter 2019 4

Question 2: Forward Checking (worth 20/100 marks)

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. Be sure that you restore all pruned values even if FC terminates after one solution.

After implementing FC you will be able to run:

python3 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.

Question 3: GacEnforce and GAC (worth 20/100 marks)

In backtracking.py you will also 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 take less time than FC on nqueens?

Question 4: AllDiff and Neq for nQueens (worth 5/100 marks)

In csp problems.py you will find the function nQueens. This function takes a model parameter that is either ’row’, ’table’ or ’alldiff’. When model == ’alldiff’ the returned CSP should contain a single n-ary all different constraint and many binary not-equals constraints.

Complete the implementation of nQueens so it properly handles the case when model == ’alldiff’ us-ing allDifferent constraints and binary not-equals constraints.

Note that this question should not take much time as you can use the class AllDiffConstraint(Constraint) and the class NeqConstraint(Constraint); these are already implemented in constraints.py.

Do you see a performance difference between ’alldiff ’ and ’row’? Why is one better than the other?
Assignment 3, University of Toronto, CSC384 – Intro to AI, Winter 2019 5

Question 5: NValues Constraint (worth 10/100 marks)

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 value from a specified set of values. For example, if we have 3 vari-ables V1, V2, V3, each with domain [1, 2, 3, 4], then the call NValuesConstraint(’test nvalues’, [V1, V2, V3], [1, 3], 1, 2) will only be satisfied by assignments such that at least 1 of the V1, V2, V3 is assigned the value 1 or 3, and at most 2 of them have been assigned the value 1 or 3.

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.

Question 6: Class Scheduling (worth 35/100 marks)

Implement a solver for the following class scheduling problem by encoding the problem as a CSP and using your already developed code to find solutions.

A student is struggling to schedule her course schedule. She has a list of courses that she wishes to take. Her schedule, like every student’s schedule, has some arbitrary number of available time slots (e.g. if a student can only have classes from 9am to 5pm, there will 40 time possible slots during the week). Classes on her list, like every class, are represented by strings that conform to the following pattern:

——

The ’type’ of class can be either a lecture or a tutorial. Your task is to assign this student a schedule of lectures and tutorials such that:

1. The student takes all the courses on her list.

2. For any given course code, the student can only enrol in one lecture and one tutorial. In addition, the student’s tutorial for a given course must be after the lecture (e.g. if the lecture is at time slot 1, the tutorial must be after time slot 1).

3. The student must have time to get from one class to another. However, some buildings are too far apart so the student cannot make it under 10 minutes (e.g. FG to FE). The student is therefore not allowed to put these two classes in consecutive time slots. Note that buildings in close proximity to one another will be encoded in an adjacency list that will accompany each scheduling problem (refer to the starter code).

4. Since the student is human, she must be rested with a certain minimum frequency. If this minimum frequency is K, then in her schedule, at least one in every consecutive set of K time slots must not have a class. If the number of courses the student must take is less than K, the constraint will be satisfied trivially.

As an example, suppose there are 6 time slots in the student’s schedule. There are 3 buildings: BA, SF, MP. Within 10 minutes the student can go between BA and MP, between BA and SF, but not between SF and MP. The student’s minimum rest frequency is 5. There are two courses she must take: CSC148, and CSC165, with the following sections:

1. CSC148-SF-3-LEC-01

2. CSC148-BA-4-TUT-01

3. CSC165-BA-2-LEC-01

4. CSC165-MP-2-LEC-02

5. CSC165-MP-5-TUT-01

6. CSC165-SF-6-TUT-02

We will represent breaks in the schedule using the string NOCLASS. A valid solution, then, will be:

[NOCLASS, CSC165-BA-2-LEC-01, CSC148-SF-3-LEC-01, CSC148-BA-4-TUT-01, CSC165-MP-5-TUT-01, NOCLASS]

Another valid solution is:

[NOCLASS, CSC165-BA-2-LEC-01, CSC148-SF-3-LEC-01, CSC148-BA-4-TUT-01, NOCLASS, CSC165-SF-6-TUT-02]

Your task is to build a CSP representation of this problem. You will then solve the CSP using any of the search algorithms you have implemented and from the solution extract a legal schedule for any given student. Note that the set of constraints you have (and have built as per previous questions) are sufficient to model this problem.

See class scheduling.py for the details of how problem instances will be specified; csp problems.py con-tains the class ScheduleProblem that will hold a specific problem.

You are to complete the implementation of solve schedules in the file csp problems.py. This function takes a ScheduleProblem, constructs a CSP, solves that CSP with backtracking search, converts the solu-tions of the CSP into the required format (see the solve schedules starter code for a specification of the output format) and then returns solutions. You can also test your code with class scheduling.py. The com-mand:

python3 class scheduling.py -a GAC -c N

where N is a problem number (ranging from 1 to 7), will invoke your code (from csp problems.py) on the specified problem. (Use python3 class scheduling.py –help for further information). It can be particularly useful to test your code on problems 1-4 in the starter code, as these problems each only test one of the constraints you have to satisfy.

HAVE FUN and GOOD LUCK!