Reference no: EM132573201

COSC 5313 Artificial Intelligence - Sam Houston State University

Assignment: Constraint Satisfaction Problems

Problem 1
Consider the following South America outline map. The task is to color the map using the four colors
red, green, blue and yellow such that no two adjacent regions take the same color.

1. Formulate this problem as a CSP. Clearly state the variables, domains, and constraints. Constraints should be specified formally and precisely, but may be implicit rather than explicit.
2. Draw the constraint graph associated with your CSP.
3. Color the map using Backtracking search with Forward Checking, and the MRV and least-constraining- value heuristics. You must show your intermediate works!

Problem 2

You are in charge of scheduling for computer science classes that meet Mondays, Wednesdays and Fridays. There are 5 classes that meet on these days and 3 professors who will be teaching these classes. You are constrained by the fact that each professor can only teach one class at a time.
The classes are:
• Class 1: 8:00-9:00am
• Class 2: 8:30-9:30am
• Class 3: 9:00-10:00am
• Class 4: 9:00-10:00am
• Class 5: 10:30-11:30am The professors are:
• Professor A, who is qualified to teach Classes 1, 2, and 5.
• Professor B, who is qualified to teach Classes 3, 4, and 5.
• Professor C, who is qualified to teach Classes 1, 3, and 4.
1. Formulate this problem as a CSP problem in which there is one variable per class, stating the domains, and constraints. Constraints should be specified formally and precisely, but may be implicit rather than explicit.
2. Draw the constraint graph associated with your CSP.
3. Your CSP should look nearly tree-structured. Solve the problem using the algorithm in ppt slide p.84 (General Algorithm for Nearly Tree-Structured CSPs). You must show your intermediate works!