Description
Introduction
There are two parts to this assignment.
1. Propagators. You will implement two constraint propagators—a Forward Checking constraint propagator, and a Generalized Arc Consistence (GAC) constraint propagator
2. Models. You will implement three different CSP models: two grid-only puzzle models, and one full
FunPuzz model (adding cage constraints to grid).
What is supplied
• cspbase.py. Class definitions for the python objects Constraint, Variable, and BT.
• propagators.py. Starter code for the implementation of your two propagators. You will modify this
file with the addition of two new procedures prop FC and prop GAC.
• puzzle csp.py. Starter code for the CSP models. You will modify three procedures in this file:
binary ne grid, nary ad grid, and caged csp model.
• csp sample run.py. This file contains a sample implementation of two CSP problems.
• tests.py. Sample test cases. Run the tests with “python3 tests.py”. This file will be released soon
after the assignment is posted.
FunPuzz Formal Description
The FunPuzz puzzle has the following formal description:
• FunPuzz consists of an n×n grid where each cell of the grid can be assigned a number 1 to n. No
digit appears more than once in any row or column. Grids range in size from 3×3 to 9×9.
• FunPuzz grids are divided into heavily outlined groups of cells called cages. These cages come with
a target and an operation. The numbers in the cells of each cage must produce the target value when
combined using the operation.
Assignment 2, University of Toronto, CSC384 – Intro to AI, Winter 2022 3
11+ 2/ 20x 6x
3- 3/
240x 6x
6x 7+ 30x
6x 9+
8+ 2/
11+ 2/ 20x 6x
3- 3/
240x 6x
6x 7+ 30x
6x 9+
8+ 2/
5 6 3 4 1 2
6 1 4 5 2 3
4 5 2 3 6 1
3 4 1 2 5 6
2 3 6 1 4 5
1 2 5 6 3 4
Figure 1: An example of a 6×6 FunPuzz grid with its start state (left) and solution (right).
• For any given cage, the operation is one of addition, subtraction, multiplication or division. Values in
a cage can be combined in any order: the first number in a cage may be used to divide the second, for
example, or vice versa. Note that the four operators are “left associative” e.g., 16/4/4 is interpreted
as (16/4)/4 = 1 rather than 16/(4/4) = 16.
• A puzzle is solved if all empty cells are filled in with an integer from 1 to n and all above constraints
are satisfied.
• An example of a 6×6 grid is shown in Figure 1. Note that your solution will be tested on n×n grids
where n can be from 3 to 9.
Additional notes:
• It is possible for a given cell to not participate in any cage constraints. That is still a valid FunPuzz
board.
• For division, we are only concerned with divisions producing integer results throughout the operation.
Assignment 2, University of Toronto, CSC384 – Intro to AI, Winter 2022 4
Question 1: Propagators (worth 55/100 marks)
You will implement Python functions to realize two constraint propagators—a Forward Checking (FC)
constraint propagator and a Generalized Arc Consistence (GAC) constraint propagator. These propagators
are briefly described below. The files cspbase.py and propagators.py provide the complete input/output specification of the two functions you are to implement.
Brief implementation description: The propagator functions take as input a CSP object csp and (optionally) a Variable newVar representing a newly instantiated Variable, and return a tuple of (bool,list)
where bool is False if and only if a dead-end is found, and list is a list of (Variable, value) tuples that have been pruned by the propagator. In all cases, the CSP object is used to access variables and
constraints of the problem, via methods found in cspbase.py.
You must implement:
prop FC (worth 25/100 marks)
A propagator function that propagates according to the FC algorithm that check constraints that
have exactly one uninstantiated variable in their scope, and prune appropriately. If newVar is None,
forward check all constraints. Otherwise only check constraints containing newVar.
prop GAC (worth 30/100 marks)
A propagator function that propagates according to the GAC algorithm, as covered in lecture. If
newVar is None, run GAC on all constraints. Otherwise, only check constraints containing newVar.
Question 2: Models (worth 45/100 marks)
You will implement three different CSP models using three different constraint types. The three different
constraint types are (1) binary not-equal; (2) n-ary all-different; and (3) FunPuzz cage. The three models
are (a) binary grid-only FunPuzz; (b) n-ary grid-only FunPuzz; and (c) complete FunPuzz. The CSP
models you will build are described below. The file puzzle csp.py provides the complete input/output
specification.
Brief implementation description: The three models take as input a valid FunPuzz grid, which is a list of
lists, where the first list has a single element, N, which is the size of each dimension of the board, and each
following list represents a cage in the grid. Cell names are encoded as integers in the range 11,…,nn and
each inner list contains the numbers of the cells that are included in the corresponding cage, followed by
the target value for that cage and the operation (0=’+’, 1=’-’, 2=’/’, 3=’*’). If a list has two elements, the
first element corresponds to a cell, and the second one—the target—is the value enforced on that cell.
For example, the model ((3),(11,12,13,6,0),(21,22,31,2,2),….) corresponds to a 3×3 board1 where
1. cells 11, 12 and 13 must sum to 6, and
2. the result of dividing some permutation of cells 21, 22, and 31 must be 2. That is, (C21/C22)/C23 =
2 or (C21/C23)/C22 = 2, or (C22/C21)/C23 = 2, etc…
1Note that cell indexing starts from 1, e.g. 11 is the cell in the upper left corner.
Assignment 2, University of Toronto, CSC384 – Intro to AI, Winter 2022 5
All models need to return a CSP object, and a list of lists of Variable objects representing the board. The
returned list of lists is used to access the solution. The grid-only models do not need to encode the cage
constraints.
You must implement:
binary ne grid (worth 10/100 marks)
A model of a FunPuzz grid (without cage constraints) built using only binary not-equal constraints
for both the row and column constraints.
nary ad grid (worth 10/100 marks)
A model of a FunPuzz grid (without cage constraints) built using only n-ary all-different constraints
for both the row and column constraints.
caged csp model (worth 25/100 marks)
A model built using your choice of (1) binary binary not-equal, or (2) n-ary all-different constraints
for the grid, together with (3) FunPuzz cage constraints. That is, you will choose one of the previous
two grid models and expand it to include FunPuzz cage constraints.
Notes: The CSP models you will construct can be space expensive, especially for constraints over many
variables, (e.g., for cage constraints and those contained in the first binary ne grid grid CSP model).
Also be mindful of the time complexity of your methods for identifying satisfying tuples, especially when
coding the puzzle csp model.
HAVE FUN and GOOD LUCK!
