Consider the following maze. The successors of each cell are the adjacent cells in the directions North (up), East (right), South (down), and West (left). No diagonal moves are permitted. You may not move from one cell to an adjacent cell when a wall (thick line) exists. For example, successors(T) = {O, Y, G} and successors(M) = {S, I, R}. You cannot move from cell M to cell N, or anywhere else a wall exists. Each move has cost 1.

Find a path from cell S to cell G. You are to write the order in which the nodes are EXPANDED, and the SOLUTION that is found. If no solution is found, say so. This is exactly the same as we did for the examples in class and in the notes. If the search method needs to break ties, expand the nodes in alphabetical order (choosing first the node corresponding to the letter closest to the front of the alphabet.) For example, if nodes D and U have the same value, node D would be expanded before node U.

The search method is Algorithm A*. Use the heuristic function h(state) = Manhattan Distance to goal. This is the same heuristic used in class for the 8-puzzle. Minimize this function. For example, h(D) = 3 and h(A) = 6 (so the thick wall does not count in computing this heuristic).

\begin{tabular}{|c|c|c|c|c|} \hline A & B & C & D & E \\ \hline F & H & I & J & K \\ \hline L & Sstart & M & N & O \\ \hline P & Q & R & Ggoal & T \\ \hline U & V & W & X & Y \\ \hline \end{tabular}