UDel CISC681/481-010 Artificial Intelligence, Fall 2009 | news | syllabus | schedule | homework | |

**Heuristics**(10 points): The Manhattan distance heuristic for the 8-puzzle is the sum of the Manhattan distances of each tile to its correct location on the 3x3 board. This heuristic is admissible.- Show that the Manhattan distance heuristic is consistent.
- Now consider a slight variation:
*h'*= the Manhattan distance heuristic plus the Manhattan distance from the blank space to the upper left space. Show that*h'*is inadmissible. - Prove that as long as a heuristic does not overestimate the cost by more than a fixed constant
*c*, the solution A* finds will have cost that exceeds the true cost by no more than*c*.

**Constraint satisfaction and logic**(20 points):- Problem 5.13 in the book lists a series of facts and asks a question to be answered. Formulate the problem as a CSP. Clearly state your variables, their domains, and the constraints.
- Sketch the first five steps of a solution to the CSP problem using backtracking, forward checking, and the MRV and least-constraining value heuristics.
- Now reformulate the given facts as a propositional logic knowledge base. Use propositional inference rules to determine the answer to the question.

**Games 1**(15 points): Problem 6.1 in the book.**Games 2**(681 students, 15 points): Problem 6.8 in the book.