Assignment 2: CSPs CSC 384H

$30.00

Category:

Description

5/5 - (6 votes)

Introduction
In this assignment you will implement two constraint propagtors. prop_FC is a procedure that given an
CSP (with constraints and variables and where some variables might be assigned) computes all variable
value pairs that would be pruned by the forward checking algorithm. Your prop_FC procedure will also
passed the variable that has been newly assigned.
The other propagator prop_GAC will implement GAC propagation.
In addition to these two propagators you will be asked to implement two different CSPs models for
solving the Sudoku problem. In one model only binary not equal constraints will be used, while in the other
model 9-ary all different constraints will be used.
What is supplied. You will be supplied with python code implementing Constraint, Variable and
BT objects. The file cspbase.py contains the class definitions for these objects. The code supports
representing constraints as a collection of satisfying tuples—so to specify a constraint in one has to construct
the list of satisfying tuples and pass them to the constraint object.
Note that this representation can be space expensive, especially for constraints over many variables, e.g.,
those contained in the second Sudoku CSP model.
You will be supplied with two template files propagators.py and sudoku csp.py which you
will complete with your implementation.
2
Propagators 50/100 marks
See the files cspbase.py and propagators.py for the input output specification of the two functions
you are to implement.
The correct implemenation of each function is worth 25/100 marks.
To Submit
1. Submit your python implementation in the file propagators.py
Question 2. Implement Model 1: worth 50/100 marks
Implement the functions sudoku_csp_model_1 and sudoku_csp_model_2. These two functions
take as input an initial Sudoku board, and construct and return a CSP model where for model 1 all constraints
are binary not-equals constraints and for model 2 all constraints are larger arity all-diff constraints. A
variable is defined for each cell of the board and a matrix of the variables is also returned by your routine.
See the file sudoku_csp.py for the detailed specification of these functions.
To Submit
1. Submit your python implementation in the file sudoku csp.py
3