Depth First Search

• This is a really simple state space, so we're going to use perhaps the simplest exhaustive algorithm, depth-first search.
• You start at S, and try a path. You remember where you've been and the other options on a stack. When you get to the goal, print off where you have been. If you reach a dead-end, backtrack by popping the stack, and try another path.
• The maze was defined by (1,G,2,3,S,4,5,6,7,8,9,10), (1-3,2-3,3-S,G-4,S-5,4-5,5-7,6-7,7-8,8-9,9-10).
• Put S on the stack, put the things it's connected to on the stack, and choose one to expand.
• Let's choose 3-S first. Repeat, expanding from 3.
• This adds 3-1, and 3-2. Pick 1.
• Pop that as it's a dead end.
• Put 2 on, then pop it as it's a dead end.
• Pop 3 as all of its paths are dead ends, and continue to the right.
• Note you have to fix this up if there are cycles, and you need a bit of note taking to print things off.