Description
Introduction
There are two parts to this assignment.
1. Propagators. You will implement two constraint propagators—a Forward Checking constraint propagator, and a Full Inference constraint propagator
2. CSP Encodings. You will implement three different CSP encodings: two grid-only puzzle encodings, and one full FunPuzz encoding (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 FI.
• puzzle csp.py. Starter code for the CSP encodings. You will modify three procedures in this file:
binary ne grid, nary ad grid, and caged csp.
• 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.
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).
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.
• 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.
Question 1: Propagators (inference algorithms) (worth 55/100 marks)
You will implement Python functions to realize two constraint propagators—a Forward Checking (FC) constraint propagator and a Full Inference (FI) 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 FI (worth 30/100 marks)
A propagator function that propagates according to the complete Inference algorithm, as covered
in lecture. If newVar is None, run inference on all variables. Otherwise, only check constraints
containing newVar.
Question 2: CSP Encodings (worth 45/100 marks)
You will implement three different CSP encodings 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 encodings
are (a) binary grid-only FunPuzz; (b) n-ary grid-only FunPuzz; and (c) complete FunPuzz. The CSP encodings you will build are described below. The file puzzle csp.py provides the complete input/output
specification.
Brief implementation description: The three encodings 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 grid ((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.
All encodings 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 encodings do not need to encode the cage
constraints.
You must implement:
binary ne grid (worth 10/100 marks)
An encoding 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)
An encoding of a FunPuzz grid (without cage constraints) built using only n-ary all-different constraints for both the row and column constraints.
caged csp (worth 25/100 marks)
An encoding 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 encodings and expand it to include FunPuzz cage constraints.
Notes: The CSP encodings 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 encoding).
Also be mindful of the time complexity of your methods for identifying satisfying tuples, especially when
coding the caged csp.
HAVE FUN and GOOD LUCK!
