Question 1 (Puzzle Solving, 35 points). Victoria is trying to solve a puzzle. In this puzzle she has an nxn board. Some of the squares are marked urith obstacles, and one of which is a designated target square. The board also has two pauns on it. As a move, Victoria may take either paun and move it as far as it goes in one of the four cardinal directions until it bumps into an obstacle, the edge of the board, or the other pawn. Her objective is to make some sequence of moves that ends with one of the pauns at the target square. For example, in the figure below, the moves shown allow her to bring paum A to the target square in 6 moves. Find an algorithm that given n, and the locations of the obstacles, pawns, and target runs in time polynomial in n and determines whether or not it is possible for Victoria to solve this puzzle. What is the runtime of this algorithm? 3 11 2 B 41 6 5