Computer Science 15-112, Fall 2011
Optional Lecture Notes: Backtracking
These notes were prepared by students attending the optional lecture on mazes. As such, they may contain a small error here or there (standard disclaimer). They are provided here as a service to those who may have missed the lecture.
First, here is the code that we
wrote: mazeSolver.py and
nQueens.py
Backtracking
Two examples:
1. Solving mazes
2. N Queens Problem
1. How are we going to solve a maze?
· Take the mazes.py code and modify it so that when “s” is hit, the maze is solved and the solution is displayed
· Exhaustive (similar to flood fill)
· Backtracking
o Put the current node on the solution path
o Try using recursion in each of the 4 directions
§ Try going down and solve the maze recursively
§ If that didn’t solve the maze, try going right…
§ If that didn’t solve the maze, try going left…
o If none of them work, take the node off the solution path and return failure
def solveMaze(maze):
(rows, cols) = (len(maze), len(maze[0]))
visited = set() #we need to keep track of all the nodes we’ve already seen using a set
def solve(row, col): #meaning go to this location and try to solve from here.
#this function will have access to the visited set because it’s in a closure
if ((row == rows-1) and (col == cols-1)): #First base case: this means you’ve made it!
return True
elif ((row,col) in visited): #Second: we have been here before, so fail
return False
else: #Third: we’re not at the end and we haven’t been here before!
The process here is going to be as follows:
· Mark nodes as visited
· Try directions recursively and return if any succeed
o See if there’s a bridge to the target
o Cross the bridge
o Recursively try to solve the maze
o If we succeeded, return True
o Otherwise, uncross the bridge and keep going
· If all the directions failed, mark node as “not visited” and fail
# 1. mark node as "visited"
visited.add((row,col))
# 2. try every direction recursively, return if ANY succeeds
for dir in [NORTH,SOUTH,EAST,WEST]:
(targetRow, targetCol) = findTarget(maze,row, col, dir)
if ((targetRow >= 0) and (targetRow < rows) and #verify that we’re on the board
(targetCol >= 0) and (targetCol < cols) and
bridgeExists(maze, row, col, dir, targetRow, targetCol)): #we need to know if there’s a bridge connecting them
# we found a bridge to a target that can be explored, so...
# 1. cross the bridge
setBridgeCrossed(maze, row, col, dir, targetRow, targetCol, True) #we need to mark the bridge as being crossed
# 2. recursively try to solve the maze from that target and if we succeed, return True (we solved from here, too!)
if solve(targetRow, targetCol):
return True
# 3. we only get here if... we failed after crossing that bridge, so, uncross the bridge and keep going
setBridgeCrossed(maze, row, col, dir, targetRow, targetCol, False)
# 3. mark node as "not visited" and fail
visited.remove((row,col))
return False
(currentRow, currentCol) = canvas.data.currentSpot
solve(currentRow, currentCol)
This is backtracking!
Try one direction recursively until infinity – if we solve it, yay! We win.
Otherwise, try a new way until we’ve tried every way exhaustively from a given node. If we’re at the end of a path that is not the solution, we back up until we have a new directional choice and try it from there.
Helper function #1:
def bridgeExists(maze, row, col, dir, targetRow, targetCol):
#similar to addBridge() from last week except row is flipped with targetRow and col is flipped with targetCol
#and this just asks IF we added a bridge
rows = len(maze)
cols = len(maze[0])
if (dir == EAST): return maze[row][col].hasEastBridge #if it has an East Bridge, just return so!
elif (dir == SOUTH): return maze[row][col].hasSouthBridge
elif (dir == WEST): return maze[targetRow][targetCol].hasEastBridge #remember we only keep track of E and S bridges
elif (dir == NORTH): return maze[targetRow][targetCol].hasSouthBridge
Helper function #2:
def setBridgeCrossed(maze, row, col, dir, targetRow, targetCol, isCrossed): #tells us whether or not it’s actually crossed
#isCrossed will just be set to True/False.
rows = len(maze)
cols = len(maze[0])
if (dir == EAST): maze[row][col].pE = isCrossed #if we uncross a bridge, set to F
elif (dir == SOUTH): maze[row][col].pS = isCrossed
elif (dir == WEST): maze[targetRow][targetCol].pE = isCrossed
elif (dir == NORTH): maze[targetRow][targetCol].pS = isCrossed
2. Solving NQueens
· What is NQueens? Given an NxN chess board, we want to lay queens down such that no queen attacks another
· Method and Observations:
o Every row and column must have 1 queen
o For a given column, try putting its queen in each row in turn:
o Before putting another queen down, we have to check if the queen will be attacked by other queens
o Once the queen is on a valid square, recursively solve the rest of the board to see if it works
o If we fail, pick up the queen and try again!
o Keep trying successive rows in the next column until we succeed (ie we’ve found a place that is not attacked)
o If we get all the way to the last row and fail, the whole column failed, so return failure
1. Returning whether or not there is a solution
def nQueens(n):
queenRow = [-1] * n #we only need a 1D list because the index is the col and the value is the corresponding row
def solve(col): #recursive function that solves column by column
if (col == n): #base case! Remember that we can use n because we’re in a closure
return True
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 xrange(n):
if isLegal(row,col): #we can ONLY place a queen if it is not attacked by another queen
queenRow[col] = row # place the queen and hope it works
if solve(col+1):
# ta da! it did work
return True
queenRow[col] = -1 # pick up the wrongly-placed queen
Picking up the wrongly-placed queen is the same as “uncrossing the bridge” from before
This is not necessary but lends clarity
return False # shoot, can't place the queen anywhere
return solve(0) #start in column 0
Now, we need to go back and define our isLegal() function! Let’s stick this inside our function above solve().
We know that two queens attack each other if they’re in the same row, column, or diagonal…
def isLegal(row, col):
# a position is legal if it's on the board (which we can assume
# by way of our algorithm) and no prior queen (in a column < col)
# attacks this position
for qcol in xrange(col):
qrow = queenRow[qcol]
if ((qrow == row) or #same row
(qcol == col) or #same col (actually impossible…)
(qrow+qcol == row+col) or #same diagonal (see below)
(qrow-qcol == row-col)): #same diagonal (see below)
return False #not legal!
return True
Pattern for diagonals: Look for where the sum (or difference) of the row and the column is constant
In the diagram below, the diagonals circled in red have constant sums of -1 and 0 while the diagonal circled in blue has a constant difference of 2.
2. Getting a solution and printing it out
Assuming there’s a solution, we want to return the solution instead of just True/False. Since the queen row is really the solution, we can just return that.
def nQueens(n):
queenRow = [-1] * n
def isLegal(row, col):
for qcol in xrange(col):
qrow = queenRow[qcol]
if ((qrow == row) or
(qcol == col) or
(qrow+qcol == row+col) or
(qrow-qcol == row-col)):
return False
return True
def make2dSolution(queenRow):
solution = [(["- "] * n) for row in xrange(n)] #we can use n because we’re in a closure! place “-“ where there’s no queen
for col in xrange(n):
row = queenRow[col]
solution[row][col] = "Q " # place Q where there’s a queen
return "\n".join(["".join(row) for row in solution]) #see below for what this will actually print!
def solve(col):
if (col == n):
return make2dSolution(queenRow) #if we’ve succeeded…
else:
for row in xrange(n):
if isLegal(row,col):
queenRow[col] = row
solution = solve(col+1) #store the solution from the recursive call
if (solution != None): #make sure there is a solution
return solution #if so, return the 2D solution!
queenRow[col] = -1
return None
return solve(0)
What will nQueens(4) actually print?
3. Returning the total number of solutions
Now, we want to view the total number of solutions for placing N queens on any NxN chess board. To see the full table of solutions, click here and scroll down to ‘Counting Solutions’: http://en.wikipedia.org/wiki/N-queens
def nQueens(n):
queenRow = [-1] * n
def isLegal(row, col):
for qcol in xrange(col):
qrow = queenRow[qcol]
if ((qrow == row) or
(qcol == col) or
(qrow+qcol == row+col) or
(qrow-qcol == row-col)):
return False
return True
def solve(col):
if (col == n):
return 1 #return an int instead of a bool to count the number of solutions as we recurse
else:
solutions = 0 #exact same as approach 1 except we’re returning solutions instead of True!
for row in xrange(n):
if isLegal(row,col):
queenRow[col] = row # place the queen and hope it works
solutions += solve(col+1) #store the solution from the recursive call
queenRow[col] = -1 # pick up the wrongly-placed queen
return solutions
return solve(0)
Then, to view the table…
print "Solution counts..."
for n in xrange(25):
print n, nQueens(n)
Note: our current method is far too slow to print the whole table. Can you do better?
Here are the bonus assignments (only open to students who attended the lecture):
#1) [2pts] fix bug in display of bridges of solution to maze
#2) [3pts] make nQueens faster, but do NOT look up online how to do it
#3) [7.5pts] solve knights tour using backtracking (do not look it up online, either!)
#4) [7.5pts] solve sudoku
submit to all three bonus graders (andrew id's posted at the lecture) at once
due wed 9-nov at 10pm
groups of up to 3 are allowed