# maze traversal puzzle

maze

## maze

solve this maze (from the internet)

• what algorithm did you use to solve it?

algorithm 0: random walk
```current cell <-- origin
while current cell != destination
current cell <-- random neighbour of current cell
print current cell
```
random walk maze traversal
• random walk maze traversal

• this implementation is recursive

• pro: easy to describe, leave some implementation details to language implementers

• con: harder to learn, lose control to language implementers (e.g. stack overflow)

analysis of algorithm
• correct? (does it always do what it is supposed to?)

• yes: every reachable location will, with positive probability, be reached

• proof: consider a path from start to goal with distance t

• assume each cell has at most k neighbours

• what is prob that we reach the goal after exactly t iterations?

• at least 1 / (k^t)

• efficient? (w.r.t. time? w.r.t. space?)

• no: if at least one nbr of start cell is not goal, then for any positive integer n, probability that there are at least n iterations is positive

• proof: start-notgoal-start-notgoal-start-notgoal …

• prob. we are on this path after n iterations at least 1/(k^n)

• can it be improved?

• keep track of visited cells

algorithm 1: random walk with remembering
```current cell <-- origin
mark current cell
while current cell != destination
current cell <-- unmarked random neighbour of current cell
mark current cell
print current cell
```
analysis of algorithm?
• correct? (does it always do what it is supposed to?)

• no: why?

• efficient?

• yes: for a maze with n cells, at most n-1 iterations (why?)

a maze and its adjacency graph
```X X X X X X    a - b - c - d
X . . . . X    |       |
X . X . X X    e       f
X . . X . X    |
X . . . . X    g - h       i
X X X X X X    |   |       |
j - k - l - m

nodes or points:  a b c ... m
edges or lines:  ab ae bc cd cf eg gh gj hk im jk kl lm
```
graph traversal
• our version

• from a given start node, see what nodes we can reach by following edges

• maintain list L of nodes seen but not yet explored

• do not add a node to a list if we have already seen it

• L is queue, FIFO list

• so remove node appended earliest

• iterative depth-first search:

• L is stack, LIFO list

• so remove node appended most recently

• depth-first search

• recursive (recurse as soon as unseen nbr found)

• differs slightly from iterative-dfs

iterative bfs,dfs
```  for all nodes v: v.seen <- False

L = [start],  start.seen = True
while not empty(L):
v <- L.remove()
for each neighbour w of v:
if w.seen==False:
L.append(w), w.seen = True
```
example trace of bfs
```use the above adjacency graph, start from node j

initialize L = [ j ]

while loop execution begins
remove j from L               L now [ ]
nbrs of j are g,k
append g to L, g.seen <- T    L now [ g ]
append k to L, k.seen <- T    L now [ g, k ]

while loop continues (bfs, so L is queue, so remove g)
remove g from L               L now [ k ]
nbrs of g are e,h,j
append e to L, e.seen <- T    L now [ k, e ]
append h to L, h.seen <- T    L now [ k, e, h ]

while loop continues: remove k from L
v <- k                        L now [ e, h ]
nbrs of k are j,h,l
append l to L, l.seen <- T    L now [ e, h, l ]

while loop continues: ...
```
exercises
• complete the above bfs trace

• hint: order in which edges are examined is jg jk ge gh gj kh kj kl …

• so order of removal from L is j g k e h l a m b i c d f

• perform an iterative dfs trace

• hint: only difference is that list is stack

recursive dfs
```  for all nodes v: v.seen <- False

def dfs(v):
v.seen <- True
for each neighbour w of v:
if w.seen==False:
dfs(w)

dfs(start)
```
example dfs trace
```use above graph, start from j

dfs(j) nbrs g,k
. dfs(g) nbrs e,h,j
. . dfs(e) nbrs a,g
. . . dfs(a) nbrs b,e
. . . . dfs(b) nbrs a,c
. . . . . a already seen
. . . . . dfs(c) nbrs b,d,f
. . . . . . b already seen
. . . . . . dfs(d) nbrs c
. . . . . . . c already seen
. . . . . . dfs(f) nbrs c
. . . . . . . c already seen
. . . . e already seen
. . . g already seen
. . dfs(h) nbrs g,k
. . . g already seen
. . . dfs(k) nbrs g,h,l
. . . . g already seen
. . . . h already seen
. . . . dfs(l) nbrs k,m
. . . . . k already seen
. . . . . dfs(m) nbrs l,i
. . . . . . l already seen
. . . . . . dfs(i) nbrs m
. . . . . . . m already seen
```
example, above maze graph, from j
```- assume nbrs are stored in alphabetic order
- iterative bfs: order of removal from list?
j g k e h l a m b i c d f
- iterative dfs: order of removal from list?
j k l m i h g e a b c f d
- recursive dfs: order of dfs() calls?
j g e a b c d f h k l m i

- iterative dfs with nbrs added to list in reverse order:
j g e a b c d f k h l m i
notice that this differs from recursive dfs
```
algorithm 2: use list to keep track of cells we have seen
• list cells examined in FIFO manner (queue)?

• list cells examined in FILO manner (stack)?

• bfs-dfs maze traversal