$1.[20$ points$]-$You are given an instance of a problem where you have an n x n grid of squares. Each square can be unpainted or can have a hole, so you cannot go on the square with a hole. The objective is to paint all the squares that do not have a hole. You start in the square $(0,0)$ which is unpainted. The actions you can do are: $(1)$ paint the square you are on if it is not painted; $(2)$ move, either vertically or horizontally, to an adjacent square inside the grid that is not painted and does not have a hole.

a$.$ Describe a state$-$space representation for the problem, specifying the

state representation, the initial state, the goal condition, and the actions.

b$.$ Is the state space finite? Is it a tree or a graph?

c$.$ Propose a heuristic for the problem. Is your heuristics admissible or not?

Explain briefly your answer.

$2.[20$ points$]$ A drawback of A$*$ is its memory requirement since the frontier might get very large. Suppose you modify A$*$ as follows: You obtain by some method a path to a goal node and its associated cost f$($Goal$)=$C$.$ This cost is not necessarily minimal but it gives an upper bound on the minimal cost. Now use A$*$ with an admissible h function and discard immediately any frontier nodes reached whose f values are greater than C$.$

a$.$ Is this modified A$*$ algorithm guaranteed to find an optimal solution if one exists? Why? What happens if there is no solution? Be precise.

b$.$ Does the fact that the algorithm discards some of the nodes in the frontier mean that fewer nodes are expanded? Why or why not? Be precise.

c$.$ Does this modified algorithm reduce the total storage requirements? Why or why not? Explain your reasoning.

$3.[20$ points$]$ Answer the following questions, justifying briefly your answers:

a$.$ Why any heuristic which is an optimal solution to a relaxed problem is

admissible and consistent?

b$.$ What is the difference between an incremental and a complete$-$state

space representation?

c$.$ Does alpha$-$beta pruning require the algorithm to generate the successors of a node one at a time or all at once? Explain what it requires and why.

d$.$ Why does the algorithm AC$-3$ put back on the queue every arc $($X$\_$i$,$X$\_$j$)$ whenever any value is deleted from the domain of X$\_$i$,$ even if each value of X$\_$j is consistent with several remaining values of X$\_$i$?$

$4.[25$ points$]$ Not to get into politics, but given the current situation I hope this will happen. Solve the following cryptoarithmetic problem

USA $+$

USSR $=$

$---$

PEACE

To solve it you need to find a mapping from letters to digits so that each letter is mapped to a different digit. The first digit in each number cannot be $0.$

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

b$.$ Solve the problem using backtracking search with proper heuristics.

c$.$ Show the results and the search tree used to solve the problem

$5.[15$ points$]$ In the following game tree show the branches that are pruned by alpha$-$beta pruning. For each branch pruned, write the condition with the specific values that are used to do the pruning. At the end indicate which move will be selected by the max player.

EXTRA CREDIT $[10$ points$]$

$1.[10$ points$]$

$1.$ Suppose you are given a map where distances between places are expressed in kilometers. You decide to convert them to miles. Will the uniform cost search algorithm find the optimal solution in the map where the distances have been converted to miles? Will it be the same solution as the one obtained using kilometers? Why?

$2.$ Suppose instead you are given a map with the cost expressed in the travel time from one place to another, expressed in minutes. You decide to add $10$ minutes to the travel time of each arc. Will the uniform cost search algorithm find the optimal solution, i$.$e$.$ the fastest solution? Will the solution be the same as the solution found before adding the extra time? Explain.