Summary This assignment covers most of the basic principles and techniques involved in solving constraint satisfaction problems. The student is required to first represent and solve a simple problem with the help of AIspace, an interactive tool for teaching and learning AI (http://www.aispace.org/). After that, the student is asked to implement several CSP techniques (Arc consistency, Search by domain splitting, Stochastic Local Search) and apply them to solve more realistic problems ranging from games (sudoku) to configuration and scheduling problems.
Topics CSP, Search, Stochastic Local Search (SLS)
Audience  First undergraduate AI course (focusing on Representation and Reasoning, not Learning)
Difficulty This is a very challenging assignment. Students are strongly encouraged to work in pairs on the programming questions. The assignment has never been offered in this form, but from past experience with similar formats it should take students between 15 and 20 hours.
Strengths Smooth increase in the complexity of the problems. AIspace helps students to interactively explore the relevant R&R techniques before they have to implement and apply those to more challenging problems.  It is comprehensive, covering techniques to solve CSP by systematic search, by constraint propagation as well as by local search.
Weaknesses Maybe too long. Require students to learn how to use AIspace, but once they have done it, they can really benefit from all the other applets.
Dependencies Search. AIspace. Java.
Variants The code for arc consistency could be given to the students; same for the code for the SLS algorithms. This would make for an assignment more focused on representation than reasoning, and on the interpretation of results. The representation of the coloring problem in AIspace could also be given to students and the focus for that question would be more on following the step by step execution of arc consistency. This would also require less AIspace learning.

As for the design, our approach is to use AIspace to scaffold learning of basic principles and techniques before moving to more challenging questions

The assignment handout

AIspace model for question 1 (to be loaded in AIspace CSP applet)

Code for Sudoku

Code for Scheduler