I need a. and b.

SCS390 - Homework 2 1. We want to build a "jigsaw puzzle solver". You are given 3 jigsaw puzzle pieces, A,B,C and a template. Your task is to place the pieces A,B,C into the grid, i.e. A1,B2,C3 would be a valid configuration. You are also given the set of pair costs which represent how much of a mismatch there is between two pieces. High cost means that these pieces don't like to be neighbors. a. Formulate this as a search problem. I.e. define the state space, \begin{tabular}{|l||l|l|} \hline 2 & & \\ \hline 1 & 2 & 3 \\ \hline \end{tabular} Successor function, initial state, goal state, step cost. Place the pieces from left to right, i.e. Empty 123. Avoid placing the Same piece twice! Reaching a goal does not necessarily mean youplacedthepiecesattheiroptimallocation.C(A,C)=3C(B,C)=5 b. Draw the search tree and write the step costs on the edges. Solve this puzzle by hand using depth first search (DFS). At every evaluation, write 1) the node you evaluate, 2) the nodes in The fringe after the evaluation, 3) the path cost for all nodes in the fringe, e.g. N12; [N1,N4,N8]; [12,34,1]