8-puzzle problem is a 33 grid with 8 tiles (not-empty cells) and 1 blank cell. The aim of this game is to rearrange cells to have the same order of the goal state with the least number of steps, see figure 1 . The allowed actions are left, right, up, and down. This problem can be solved using a variety of search techniques. However, you are required to use the A heuristic algorithm. The only difference between the A and UCS algorithms' implementarions is the cost of the path. You might use the following pseudocode. Figure It an instance of the 8. puxzale ppoblem (start and goal states) A+Algorithm pacudacosle: Dotes: 1. The total cost of the path f=g+h a. g cost is the path cost which is the number of steps from the initial state to the current state in the path b. h cost is a heuristic value which can be computed in different ways, we will solve the problem using 2 different ways i. The number of misplaced cells between current node and goal node (zero value is not counted) ii. Then you are supposed to recompute the heuristic value using Manhattan distance between the misplaced cells elearning.yu.edu.jo // Generate children Expand the current state by moving the blank cellin all possible directions for each child in the children // child is on the visiteduist Arilicial laucligenor Fall: if child is in the visitedilat continue // Child is already in queuelist if child is in the quevelist's nodes if the child.g is higher than the openuist node"s g continue Diores: 1. The total cost of the path f=g+h a. g cost is the path cost which is the number of steps from the initial state to the current state in the path b. h cost is a heuristic value which can be computed in different ways, we will solve the problem using 2 different ways i. The mumber of misplaced cells between current node and goal node (zero value is not counted) ii. Then you are supposed to recompute the heuristic value using Manhattan distance between the misplaced cells 1. Manhattan distance, d=x2x1+y2y1 2. Heuristic value, h=k=0nxk,gxk,s+yk,gyk,s a. n the size of the puzzle, in our case it is 8 b. xk,g the x value of the number k in the goal state c. xk,3 the x value of the number k in the goal state d. yk,g the y value of the number k in the goal state e. yk,s the y value of the number k in the goal state Questions: 1. Write the code of A algorithm based on the pseudocode initially with h equals the number of misplaced cells. 2. Are there any logical errors in the mentioned pseudocode? 3. Use Manhattan distance to recompute h value as mentioned above. 4. For the following configuration, what is the number of steps required to solve the puzzle
