In 1942, Anthony S. Filipiak made a 10 block sliding puzzle called the Traffic Cop Tangle. The point of this puzzle is to swap the positions of the blocks labeled `A' and `B', by sliding around the pieces into the empty space (the unlabeled space between the A and the B). Note: pieces can be moved more than one position in one move (e.g. square #4 below could be moved either one or two positions into the empty space)

1. [8 points] The start state is shown in Figure 3. Provide the rest of the state-based

representation of this problem as a search problem: (a) [3pts] What is a state? (b) [3pts] An action? (c) [1pt] A goal-state? (d) [1pt] A solution?

2. [4 points] Draw the first three levels (root counts as 1) of a breadth-first search (with cycle checking) from the start state in Figure 3. Label the actions on the arcs, but just use shaded ovals for nodes (rather than writing or drawing the state).

3. [7 points] (a) [3pts] Give a heuristic which is admissible and can be evaluated in polynomial time; (b) [4pts] explain why your heuristic is admissible. More points will be given to heuristics which are better approximations of actual path costs.

4. [6 points] (a) [2pts] What is a suitable search strategy to use for this graph? (b) [4pts] Why?

In 1942, Anthony S. Filipiak made a 10 block sliding puzzle called the Traffic Cop Tangle. The point of this puzzle is to swap the positions of the blocks labeled 'A' and 'B', by sliding around the pieces into the empty space (the unlabeled space between the A and the B). Note: pieces can be moved more than one position in one move (e.g. square #4 below could be moved either one or two positions into the empty space) 1 2 Figure 3: Traffic Cop Tangle: initial configuration of pieces 1. [8 points] The start state is shown in Figure 3. Provide the rest of the state-based representation of this problem as a search problem: (a) [3pts] What is a state? (b) (3pts] An action? (c) [1pt] A goal- state? (d) [1pt] A solution? 2. [4 points) Draw the first three levels (root counts as 1) of a breadth-first search (with cycle checking) from the start state in Figure 3. Label the actions on the arcs, but just use shaded ovals for nodes (rather than writing or drawing the state). 3.[7 points] (a) [3pts] Give a heuristic which is admissible and can be evaluated in polynomial time; (b) [4pts) explain why your heuristic is admissible. More points will be given to heuristics which are better approximations of actual path costs. 4. [6 points] (a) [2pts] What is a suitable search strategy to use for this graph? (b) [4pts] Why? In 1942, Anthony S. Filipiak made a 10 block sliding puzzle called the Traffic Cop Tangle. The point of this puzzle is to swap the positions of the blocks labeled 'A' and 'B', by sliding around the pieces into the empty space (the unlabeled space between the A and the B). Note: pieces can be moved more than one position in one move (e.g. square #4 below could be moved either one or two positions into the empty space) 1 2 Figure 3: Traffic Cop Tangle: initial configuration of pieces 1. [8 points] The start state is shown in Figure 3. Provide the rest of the state-based representation of this problem as a search problem: (a) [3pts] What is a state? (b) (3pts] An action? (c) [1pt] A goal- state? (d) [1pt] A solution? 2. [4 points) Draw the first three levels (root counts as 1) of a breadth-first search (with cycle checking) from the start state in Figure 3. Label the actions on the arcs, but just use shaded ovals for nodes (rather than writing or drawing the state). 3.[7 points] (a) [3pts] Give a heuristic which is admissible and can be evaluated in polynomial time; (b) [4pts) explain why your heuristic is admissible. More points will be given to heuristics which are better approximations of actual path costs. 4. [6 points] (a) [2pts] What is a suitable search strategy to use for this graph? (b) [4pts] Why