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

Question

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.

Solution 1

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.

Solution 2

Use the power of Python! I propose to yield your found solutions instead of returning them. This way you've created a generator for all solutions. To make a list out of this is pretty straight forward then (in case you really need it) by the notation

[ solution for solution in solve(4) ]

or simply

list(solve(4))

EDIT:

In your case solve() and place_queen() must be made generators. In solve() you should do as last thing: return place_queen(board, 0, 0). By this you return a generator. (You could also do for solution in place_queen(board, 0, 0): yield solution but that would just relay the yielded values.)

In place_queen() instead of the returns like return place_queen(board, row+1, 0) you should do things like for solution in place_queen(board, row+1, 0): yield solution.

EDIT2:

#!/usr/bin/env python

def solve(n):
    #prepare a board
    board = [[0 for x in range(n)] for x in range(n)]
    #set initial positions
    return 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:
        yield 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
            for solution in place_queen(board, row+1, 0):
                yield solution
            return
        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
            for solution in place_queen(board, row-1, c+1):
                yield solution

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

import sys, pprint
sys.setrecursionlimit(10000)
for solution in solve(8):
    pprint.pprint(solution)

Comments

[Maximus S]

This is an interesting approach. However, replacing all return with yield results in a place_queen generator object while I expected I would get a generator of list instead (which makes your solution work). Maybe there's something I don't understand about generators. Do you have an idea?

[Alfe]

Of course if you yield something, then you are a generator, not a mere function. Whoever uses you then should iterate over you and not just expect to get a value. Instead of solution = solve(4) one should do sth like for solution in solve(4): print solution or similar.

[Alfe]

Unfortunately your code does not work out of the box (complains about missing variable queens in is_safe()), otherwise I would have adopted my approach quickly to your code.

[Maximus S]

This method does not seem to work because without a return statement in each loop inside place_queen(), row keeps increasing and you get a index out of range error.

[Maximus S]

By the way, code is edited so it works just fine if you copy & paste it.

[Maximus S]

Thanks for a great answer. Like you said, I would be better off with a simpler board representation. I updated my code. Would you mind looking at it and answering the added questions?

[Blckknght]

@MaximusS: I've edited with answers to your additional questions and some additional comments on your latest code.

[Maximus S]

Also, I've heard from somewhere that I should avoid using deepcopy(). Do you know why this is?

[Blckknght]

@MaximusS: Well, you generally want to avoid copying data if you don't need to, simply because it tends to be slow (and for the obvious reason that it increases your program's memory usage). But if you need to copy a complex object, copy.deepcopy is probably the best way to do it. For simple objects like (non-nested) lists you can copy in other ways (like list(old_lst) or old_lst[:]) but that won't be enough for a nested structure like board.

[Maximus S]

Thanks for your tremendous help. I just posted another question that's along the same lines with this one. Take a look when you have some free time. stackoverflow.com/questions/20536523/…

[Alfe]

I adopted my method to your solution and pasted the resulting code. It finds 92 solutions for an 8×8 chessboard which is due to symmetries.