Homework Assignment #2: Constraint Satisfaction Solution

Description

Evaluation Details

We will test your code electronically. You will be supplied with a testing script that will run a subset of the tests (tests.py). If your code fails all of the tests performed by the script (using Python version 3.5.2), 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.

We will set a timeout of 60 seconds per board during marking. This 60 second time limit includes the time to create a model and find a solution. Solutions that time-out are considered incorrect. Ensure that your implementations perform well under this limit, and be aware that your computer may be quicker than teach.cs (where we will be testing). We will not conduct end to end tests on boards with constraints whose domain is larger than six.

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.5.2) using only standard imports. 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 two parts to this assignment.

1. Propagators. You will implement two constraint propagators—a Forward Checking constraint prop-agator, and a Generalized Arc Consistence (GAC) constraint propagator—and three heuristics— Minimum-Remaining-Value (MRV), Degree (DH), and Least-Constraining-Value (LCV).

2. Models. You will implement three different CSP models: two grid-only KenKen models, and one full KenKen puzzle 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.

heuristics.py. Starter code for the implementation of the variable ordering heuristic, MRV; and the value heuristic, LCV. You will modify this file with the addition of the new procedures ord mrv, ord dh, and val lcv.

• Note that cell indexing starts from 1, e.g. 11 is the cell in the upper left corner.