Extra Topic: More Backtracking
Maze Solving + N Queens

1. maze solving
   Python code: maze-solver.py
   Key excerpt:
   def solve(row,col): # base cases if (row,col) in visited: return False visited.add((row,col)) if (row,col)==(targetRow,targetCol): return True # recursive case for drow,dcol in [NORTH,SOUTH,EAST,WEST]: if isValid(data, row,col,(drow,dcol)): if solve(row+drow,col+dcol): return True visited.remove((row,col)) return False


2. nQueens
   Python code: nQueens.py
   Key excerpt:
   def nQueensSolver(col, queenRow): # Recursive backtracker for nQueens that tries to insert a queen into column # col, where queenRow keeps track of the row # of the queen in each column if (col == n): return nQueensFormatSolution(queenRow) else: # try to place the queen in each row in turn in this col, # and then recursively solve the rest of the columns for row in range(n): if nQueensIsLegal(row, col, queenRow): queenRow[col] = row # place the queen and hope it works solution = nQueensSolver(col+1, queenRow) if (solution != None): # ta da! it did work return solution queenRow[col] = -1 # pick up the wrongly-placed queen # shoot, can't place the queen anywhere return None