| START | 
| END |
Problem 1: Solve the maze below.
| START |
| END |
Problem 2: Think of the process you use when solving the maze and answer the following questions.
How do you identify when you've taken a wrong path?
What do you do when this happens; for example, do you go back to the beginning of the maze and start over?
How do you know when you have finished the maze?
How do you distinguish between taking a wrong path and reaching the end of the maze?
Consider the simplified grid maze below. Each white square represents a
position you may be in the maze, and the black squares represent walls or
obstacles in the maze and you cannot occupy them. The maze begins at the
square marked START, and ends at the square marked END. At
each position square, you have at most four possible positions you can move
to -- north, south, east, or west. Some of these may be squares you have
already been in (such as the one you just moved from).
We can number or index each square by its row and column. In this maze, the START square has index (1,1) and the END square has index (4,4). The squares (0,0), (0,1), (0,2), (0,3), (0,4) comprise the upper wall of the maze.
We can model all the possible paths through the maze using a decision tree. The root of the tree will be at the START square, and the leaves of the tree will either be "dead ends" or the END square. Each node in the decision tree will have at most three branches representing directions leading to squares you haven't yet occupied. Nodes at the same depth in the tree should be the same number of steps away from the START. Black squares do not appear in the tree.
Problem 3: Draw the decision tree for the simplified grid maze. Use the index notation for the grid squares to identify nodes in the tree.
Problem 4: Answer the same questions from Problem 2 for the decision tree of the simplified grid maze.