$1.15$points You are given the $8-$queen problem. The queens have to be placed on a chess board in such a way than no queen can attack another, where a queen attacks any piece in the same row, column, or diagonal.

a$.$Describe a state$-$space representation for the problem, specifying the initial state, goal condition, and actions.

b$.$What search algorithm would you use to solve the problem? Explain your choice.

$2.30$points: Questions on search algorithms $($with different numbers of points$)$:

a$.[5$points$]$Does Uniform Cost search expand more nodes than A$*?$Why $($or why not$)?$

b$.[10$points$]$How can hill climbing be prevented from wandering forever when it reaches a plateau?

c$.[5$points$]$You are given the following heuristic for a TSP problem: for each city n$,$h$($n$)$is the distance to the closest city not yet visited. Is this heuristics admissible? Explain briefly your answer.

d$.[10$points$]$Specify if depth limited search can find an optimal solution. If yes, under what conditions? if not, why not?

$4.20$points

Answer the following questions about CSP problems and backtracking search. Justify briefly your answers:

a$.$What is the AllDiff constraint? When would you use it$?$

b$.$When and why should the minimum remaining value heuristic be used?

c$.$When and why should the degree heuristics be used?

d$.$Why the least constraining value heuristics is used to select the value of a variable?

$5.20$points

Solve the the following cryptoarithmetic problem, finding a mapping from letters to digits, so that each letter is mapped to a different digit. Recall that the first digit in each number cannot be $0.$

THIS $+$

IS $=$

$--------$

HERE

a$.$Write the constraint equations for the problem $($remember to use the carry when doing additions$).$

b$.$Solve the problem using backtracking search and, when possible the Minimum Re$-$maining Value heuristics. Show the search tree to solve the problem.

$6.10$points Extra Credit

You have to solve a CSP where you need to guarantee arc$-$consistency. An example is the line labeling problem shown here where edges connecting vertices need to have the same label. Which algorithm would you use? Why? Can you specify one or two examples of problems where you should use arc consistency?

$6.10$points Extra Credit

You have to solve a CSP where you need to guarantee arc$-$consistency. An example is the line labeling problem shown here where edges connecting vertices need to have the same label. Which algorithm would you use? Why? Can you specify one or two examples of problems where you should use arc consistency? $6.10$ points Extra Credit

You have to solve a CSP where you need to guarantee arc$-$consistency. An example is the line labeling problem shown here where edges connecting vertices need to have the same label. Which algorithm would you use? Why? Can you specify one or two examples of problems where you should use arc consistency?