Homework 1 CSE592 Applications of AI
Name:
1. Subscribe to the class mailing list cse592 by sending mail to majordomo@cs.washington.edu with the body "subscribe cse592"
2.
A)
Write out the binary constraints which ensure 3 coloring of the following graph (I.e. color each of the nodes red, green or blue so that no nodes connected by an edge have the same color)
Example for case where there are two nodes:
Domain of V1,V2 is R,G,B
possible values of V1,V2 are (R,G), (R,B) (R,R) ...
Note: you will need to write these out in a special form to use the applet mentioned below so you may want to visit that site before writing out the constraints.
B)
At the web address http://liawww.epfl.ch/~torrens/Project/JCL/jclhome.html there is a binary constraint solving applet (click on the demonstration link).
If you do not have a browser that supports java, you can use microsoft explorer on the computers in Sieg 232
Test the constraints you've written for the above graph at this site and see if they can be solved.
Test the constraints for the 10 queens problem which is given as a demo at this site. Try the basic solver and then try the solver with forward checking. Which is faster? In one sentence, describe why it is faster.
3) The 8-puzzle problem
This question describes the use of search techniques for solving the 8 puzzle toy. The object of the toy is to slide tiles horizontally or vertically into a blank location with the goal of eventually reaching the configuration given on the right below. The arrow shows the move of sliding the 8 tile into the blank slot.
A) Assume we couch the 8 puzzle problem as state space search as described in class. Assume there is no checking for cycles. For the following methods, state if 1) they will always find a solution to the problem and 2) if they will always find the optimal solution (Ie the one which requires the fewest number of moves)
B) State whether the following heuristics are admissable and briefly why or why not