CSE 473: Artificial Intelligence I

CSE Home

About Us

Search

Contact Info

Administration  Course Index  Syllabus  Email Archive  Schedule as RSS

Problem Set #3 Due: Oct 15th at the beginning of class. Problem: Implement a CSP and run it on the "Zebra Puzzle" as described in Exercise [5.13]. Both backtracking (BT) and forward checking (FC) must be implemented, but other techniques (MRV, Min-Conflict, or other heurisitcs) are not speficically required. The goal is to get a performance comparison between backtracking with and without forward checking. The performance comparison will be made based on number of consistency checks required per run (for an example, see Figure 5.5, row three for BT and FC). Hints: Think carefully about the problem representation. You may discuss it with your classmates, but the implementation needs to be entirely your own. Write Up Guidelines: Please follow these guidelines; it is my hint to you on how to get the most points. Please bold face each section, and discuss each sub-point. If you do not follow this format and the guidelines, you will not get full credit. Problem sets must be typed, printed on hard copy, and legible. Design Overview: How did you represent the problem? Briefly explain your representation of the variables, constraints, and the constraint graph. How do you represent the constraint graph? If you don’t explicitly use a graph, how to you achieve this effect. Implementation Details: How do you keep track of what values are bound to which variables at any given time? How do you ensure consistency? How often do you do this? How do you use the constraint graph during this step? Discuss your notion of a "state" - what information is propagated form one to the next? How do you implement forward checking? Data / Tables: Recreate the table on page 143 (figure 5.5) for the Zebra problem Write a few words interpreting the results. Why was one method better than the other? Was this the result you expected? Personal assessment: If your program doesn't work, talk about what went wrong, where you got hung up, and what you would need to do to fix it. You can still get most of the points on this assignment if you do a great write-up where you discuss all the issues at hand. Extra Credit: Discuss anything extra you did you did that you would like to have considered for extra credit. No extra credit will be giving for anything not discussed in this section. Ideas for extra credit include implementing an additional CSP feature (MRV, min-conflicts, etc.) and including it in the comparison table. You migh perhaps consider implementing a generic CSP capable of solving 3-SAT problems. Code: Please put all your code at the end of your write-up. When explaining your implementation, please don't just say "Please see code" in your write-up; I don't want to have to flip through your code to look for this. Please print your code out in landscape mode, two column, double sided – this will make the stack much smaller and save paper.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to bdferris]