1. Forthesearchproblemwiththefollowingstatespacegraph,give the solution found by the A* search as well as the order of the states that the algorithm expands. Let us assume the tie is broken alphabetically.
2. FortheN‐Queensproblem,apartfromtherepresentationgivenin the lecture, please give another representation?
3. Considerthefollowingthe4x4Sudokuproblem,whereeach column, each row, and each of the four regions contain all of the digits from 1 to 4. Use backtracking search with forward checking and ordering to solve this problem. Give the order of all states to be visited. Let us assume that tie of cells is broken first from top to bottom and then from left to right, and tie of numbers is broken numerically.
3
4
2
4