Maximus S Maximus S - 4 months ago 14
Python Question

N-queen backtracking in Python: how to return solutions instead of printing them?

def solve(n):
#prepare a board
board = [[0 for x in range(n)] for x in range(n)]
#set initial positions
place_queen(board, 0, 0)

def place_queen(board, row, column):
"""place a queen that satisfies all the conditions"""
#base case
if row > len(board)-1:
print board
#check every column of the current row if its safe to place a queen
while column < len(board):
if is_safe(board, row, column):
#place a queen
board[row][column] = 1
#place the next queen with an updated board
return place_queen(board, row+1, 0)
else:
column += 1
#there is no column that satisfies the conditions. Backtrack
for c in range(len(board)):
if board[row-1][c] == 1:
#remove this queen
board[row-1][c] = 0
#go back to the previous row and start from the last unchecked column
return place_queen(board, row-1, c+1)

def is_safe(board, row, column):
""" if no other queens threaten a queen at (row, queen) return True """
queens = []
for r in range(len(board)):
for c in range(len(board)):
if board[r][c] == 1:
queen = (r,c)
queens.append(queen)
for queen in queens:
qr, qc = queen
#check if the pos is in the same column or row
if row == qr or column == qc:
return False
#check diagonals
if (row + column) == (qr+qc) or (column-row) == (qc-qr):
return False
return True

solve(4)


I wrote Python code for N-queen problem and it prints every possible solution whenever it's found. However, I would like to modify this code so that it returns a list of all the solutions(board configurations) instead of printing them. I tried modifying the code like following:

def solve(n):
#prepare a board
board = [[0 for x in range(n)] for x in range(n)]
#set initial positions
solutions = []
place_queen(board, 0, 0, solutions)

def place_queen(board, row, column, solutions):
"""place a queen that satisfies all the conditions"""
#base case
if row > len(board)-1:
solutions.append(board)
return solutions
#check every column of the current row if its safe to place a queen
while column < len(board):
if is_safe(board, row, column):
#place a queen
board[row][column] = 1
#place the next queen with an updated board
return place_queen(board, row+1, 0, solutions)
else:
column += 1
#there is no column that satisfies the conditions. Backtrack
for c in range(len(board)):
if board[row-1][c] == 1:
#remove this queen
board[row-1][c] = 0
#go back to the previous row and start from the last unchecked column
return place_queen(board, row-1, c+1, solutions)


However, this returns as soon as the first solution is found, so
solutions
only consists of one possible board configuration. Since print vs. return has been confusing to me for backtracking algorithms, I would very much appreciate it if someone could show me how to modify the above code, and how to approach similar problems in future.

I assume using a global variable would work, but I learned from somewhere that using global variables for such problem is discouraged. Could someone explain this too?

EDIT:

def solve(n):
#prepare a board
board = [[0 for x in range(n)] for x in range(n)]
#set initial positions
solutions = list()
place_queen(board, 0, 0, solutions)
return solutions

def place_queen(board, row, column, solutions):
"""place a queen that satisfies all the conditions"""
#base case
if row > len(board)-1:
#print board
solutions.append(deepcopy(board)) #Q1
#check every column of the current row if its safe to place a queen
while column < len(board):
if is_safe(board, row, column):
#place a queen
board[row][column] = 1
#place the next queen with an updated board
return place_queen(board, row+1, 0, solutions) #Q2
else:
column += 1
#there is no column that satisfies the conditions. Backtrack
for c in range(len(board)):
if board[row-1][c] == 1:
#remove this queen
board[row-1][c] = 0
#go back to the previous row and start from the last unchecked column
return place_queen(board, row-1, c+1, solutions) #Q3


The above returns all the found solutions instead of printing them. I have a few more questions (related parts are marked Q1 and Q2 in above code)


  1. Why do we need to
    solutions.append(deepcopy(board))
    ? In other words, what exactly is happening when we do
    solutions.append(board)
    and why does this lead to appending the initial board which is
    [[0,0,0,0] ...]
    ?

  2. Why do we run into a problem when
    return place_queen(board, row+1, 0)
    is replaced by
    place_queen(board, row+1, 0)
    ? We are not actually returning anything (or
    None
    ), but without
    return
    the list goes out of index.


Answer

You need to adapt your code to backtrack after a solution is found, rather than returning. You only want to return when you find yourself backtracking off the first row (because that indicates that you've explored every possible solution).

I think this is easiest to do if you change the structure of your code a bit and loop unconditionally over the columns, with the backtracking logic kicking in when you're out of bounds on either the row or column:

import copy

def place_queen(board, row, column, solutions):
    """place a queen that satisfies all the conditions"""
    while True: # loop unconditionally
        if len(board) in (row, column): # out of bounds, so we'll backtrack
            if row == 0:   # base case, can't backtrack, so return solutions
                return solutions
            elif row == len(board): # found a solution, so add it to our list
                solutions.append(copy.deepcopy(board)) # copy, since we mutate board

            for c in range(len(board)): # do the backtracking
                if board[row-1][c] == 1:
                    #remove this queen
                    board[row-1][c] = 0
                    #go back to the previous row and start from the next column
                    return place_queen(board, row-1, c+1, solutions)

        if is_safe(board, row, column):
            #place a queen
            board[row][column] = 1
            #place the next queen with an updated board
            return place_queen(board, row+1, 0, solutions)

        column += 1

This will work for small boards (like 4), but you'll hit Python's recursion limit if you try it for larger board sizes. Python doesn't optimize out tail recursion, so this code builds up a lot of stack frames as it shifts from one row to another.

Fortunately, tail recursive algorithms are usually easy to turn into iterative algorithms. Here's how that can be done to the code above:

import copy

def place_queen_iterative(n):
    board = [[0 for x in range(n)] for x in range(n)]
    solutions = []
    row = column = 0

    while True: # loop unconditionally
        if len(board) in (row, column):
            if row == 0:
                return solutions
            elif row == len(board):
                solutions.append(copy.deepcopy(board))

            for c in range(len(board)):
                if board[row-1][c] == 1:
                    board[row-1][c] = 0

                    row -= 1     # directly change row and column, rather than recursing
                    column = c+1
                    break        # break out of the for loop (not the while)

        elif is_safe(board, row, column):   # need "elif" here
            board[row][column] = 1

            row += 1      # directly update row and column
            column = 0

        else:             # need "else" here
            column += 1   # directly increment column value

Note that the iterative version doesn't need to be called with different row and column starting values, so those aren't needed as parameters. Similarly, the board and result list setup can be done before starting the loop, rather than in a helper function (further reducing the function parameters).

A slightly more Pythonic version of this would be a generator that yields its results, rather than collecting them up in a list to return at the end, but that only requires a few minor changes (just yield instead of calling solutions.append). Using a generator might also let you skip copying the board each time you have a solution, as long as you can depend on the generator's consumer using the result immediately (or making its own copy) before it advances the generator again.

Another idea would be to simplify your board representation. You know that there can only ever be a single queen in a given row, so why not just store the column where it has been placed in a one-dimensional list (with a sentinel value, like 1000 indicating no queen having been placed)? So [1, 3, 0, 2] would be a solution to the 4-queens problem, with queens at (0, 1), (1, 3), (2, 0) and (3, 2) (you could get these tuples with enumerate, if you needed them). This lets you avoid the for loop in the backtracking step, and probably makes checking if a square is safe easier too, since you don't need to search the board for the queens.

Edit to address your additional questions:

At point Q1, you must deep copy the board because otherwise you'll end up with a list of references to the same board. Compare:

board = [0, 0]
results.append(board)    # results[0] is a reference to the same object as board
board[0] = 1             # this mutates results[0][0] too!
result.append(board)     # this appends another reference to board!
board[1] = 2             # this also appears in results[0][1] and result[1][1]

print(board)   # as expected, this prints [1, 2]
print(results) # this however, prints [[1, 2], [1, 2]], not [[0, 0], [1, 0]]

As for Q2, you need to return to stop the code from running further. You could separate the return statement from the recursive call, if you want to make it more clear that the return value is not significant:

place_queen(board, row+1, 0)
return

Note that your current code may work, but it's doing some dubious stuff. You're calling is_safe with row values that are out of bounds (row == len(board)), and it's only because your is_safe implementation reports them as unsafe (without crashing) that you backtrack appropriately. And when you're in the backtracking code at row 0 (at the very end of the run), you only quit correctly because the for loop can't find any 1 values in board[-1] (that is, the last row). I suggest refactoring your code a bit more to avoid relying on such quirks for correct operation.