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

 

:Screen shot 2011-11-07 at 11.33.41 PM.png

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.

:Scan.tiff

 

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?

:Screen shot 2011-11-08 at 12.42.27 AM.png

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