Description
Introduction
There are two parts to this assignment
1. the implementation of two constraint propagators – a Forward Checking constraint propagator, and
a Generalized Arc Consistence (GAC) constraint propagator,
2. the encoding of two different CSP models to solve the logic puzzle, “Tenner Grid”, as described
below. In one model you will use binary not-equal constraints for row constraints, while in the other
model you will use n-ary all-different constraints for them.
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, to realize Forward Checking
and GAC, respectively.
• tenner csp.py – starter code for the two Tenner Grid CSP models.
• Sample test cases for testing your code. Test cases for Q1 will be released on the A2 web page on
Friday, February 10; test cases for Q2 will be released on the A2 web page on Monday, February 13.
Tenner Grid Formal Description
The Tenner Grid puzzle1 has the following formal description:
• Tenner Grid (also known as “From 1 to 10”, “Zehnergitter”, “Grid Ten”) consists of a rectangular
grid of width ten cells, i.e., the grid with dimensions n rows by 10 columns, and a special (n+1)-th
row. The task is to fill in the first n rows so that every row contains the digits 0 through 9. In columns
the numbers may be repeated.
1http://www.cross-plus-a.com/html/cros7tng.htm
Assignment 2, University of Toronto, CSC384 – Intro to AI, Winter 2017 3
6 1 5 7 3
9 7 2 1
0 1
9 0 7 3 5 4
6 5 0
21 26 21 21 29 10 28 26 21 22
6 4 1 5 7 0 8 9 3 2
5 9 7 3 6 2 1 4 0 8
3 2 4 8 5 0 9 7 6 1
1 9 6 0 7 8 3 5 4 2
6 2 3 5 4 0 7 1 8 9
21 26 21 21 29 10 28 26 21 22
Figure 1: An example of a 5×10 grid with its start state (left) and solution (right).
• The (n+1)-th row contains numbers which give the sum of the numbers in their respective columns.
The numbers in the (n+1)-th row are always given in the start state.
• The digits in adjacent cells (even diagonally adjacent cells) must be different. For example, cell(0,0)
is adjacent to cell(0,1), cell(1,0) and cell(1,1).
• The start state of the puzzle has some spaces already filled in.
• A puzzle is solved if all empty cells are filled in with an integer from 0 to 9 and all above constraints
are satisfied.
• An example of a 5×10 grid is shown in Figure 1. Note that your solution will be tested on n×10
grids where n can be from 3 to 8.
Question 1: Propagators (worth 50/100 marks)
You will implement python functions to realize two constraint propagators – a Forward Checking 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.
The correct implementation of each function is worth 25/100 marks.
Brief implementation description: A Propagator Function takes as input a CSP object csp and (optionally) a variable newVar representing a newly instantiated variable. The CSP object is used to access
the variables and constraints of the problem (via methods found in cspbase.py). A propagator function
returns 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. You must implement:
prop FC A propagator function that propagates according to the Forward Checking (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. Else, if newVar=var only check constraints containing newVar.
prop GAC A propagator function that propagates according to the Generalized Arc Consistency (GAC)
algorithm, as covered in lecture. If newVar is None, run GAC on all constraints. Else, if newVar=var
only check constraints containing newVar.
Assignment 2, University of Toronto, CSC384 – Intro to AI, Winter 2017 4
Question 2: Tenner Grid Models (worth 50/100 marks)
You will implement two different CSP encodings to solve the logic puzzle, Tenner Grid. In one model
you will use only binary not-equal constraints apart from the arithmetic sum constraints, while in the other
model you will use both binary not-equal and n-ary all-different constraints. These CSP models are briefly
described below. The file tenner csp.py provides the complete input/output specification for the two
CSP encodings you are to implement.
The correct implementation of each encoding is worth 25/100 marks.
Brief implementation description: A Tenner Grid Model takes as input a valid Tenner Grid board,
which is a tuple: (n grid, last row), and returns a CSP object, consisting of a variable corresponding to each cell of the grid. The n grid variable consists of a list of n length-10 lists, representing the first
n rows of the Tenner Grid. The last row variable is a list of 10 integers, representing the (n+1)-th row
of the grid. The variable domain of that cell is {0,…,9} if the grid is unfilled at that position (denoted by
-1 in the input), and equal to i if the grid has a fixed number i at that cell. All appropriate constraints will
be added to the board as well. You must implement:
tenner csp model 1 A model built using only binary not-equal constraints for the row and contiguous
cells constraints, and n-ary sum constraints.
tenner csp model 2 A model built using a combination of n-ary all-different constraints for the row
constraints, n-ary sum constraints, as well as binary not-equal constraints for the contiguous cells
constraints.
Caveat: The Tenner Grid CSP models you will construct can be space expensive, especially for constraints
over many variables, (e.g., for sum constraints and those contained in the second Tenner Grid CSP model).
HINT: Also be mindful of the time complexity of your methods for identifying satisfying tuples, especially
when coding the second Tenner Grid CSP model.
HAVE FUN and GOOD LUCK!
