Notes
Outline
Jan 6, 2000
Mazes are “Graphs”
A Maze
Random Solver (pseudocode)
Random’s Solution path
Claim: always have a path from startNode to currNode
à
currNode=exitNode, we have a solution
Proof by Induction
Restatement: after i moves
Base case:
0 moves (currNode=startNode)
Induction step:
have path for i moves
prove for i+1 moves.
Depth First Search is “Backtracking”
Memory usage and Locality