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 the N-queen problem, and it prints every possible solution whenever it finds. However, I would like to modify this code to return a list of all solutions (board configurations) instead of printing them. I tried to change the code as follows:

 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, therefore solutions consists of only one possible configuration of the board. Since print vs. return is confusing for backtracking algorithms, I would really appreciate it if someone could show me how to change the code above and how to deal with similar problems in the future.

I assume that using a global variable will work, but from somewhere I found out that using global variables for such a problem is not recommended. Can anyone 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 found solutions instead of printing them. I have a few more questions (related parts are marked with Q1 and Q2 in the above code)

• Why do we need solutions.append(deepcopy(board)) ? In other words, what exactly happens when we make solutions.append(board) and why does this lead to the addition of an initial board that is [[0,0,0,0] ...] ?
• Why do we encounter a problem when return place_queen(board, row+1, 0) is replaced by place_queen(board, row+1, 0) ? We do not return anything (or None ), but without return list goes beyond the index.

Answer 1

You need to adapt your code to return after the solution is found, not returned. You only want to come back when you find yourself stepping back from the first line (because it indicates that you have studied all the possible solutions).

I think this is the easiest way to do this if you change the structure of your code a bit and loop into columns, and the reverse tracking logic will start when you are outside 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 (e.g. 4), but you will fall into Python's recursion limit if you try it for large board sizes. Python does not optimize tail recursion, so this code creates many stack frames when it moves from one line to another.

Fortunately, tail recursive algorithms usually easily turn into iterative algorithms. Here's how to do it with 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 

Please note that the iterative version does not need to be called with different initial values ​​of rows and columns, therefore they are not needed as parameters. Similarly, the setup of the board and the list of results can be performed before the start of the cycle, and not in an auxiliary function (further reduce the functional parameters).

A slightly more Pythonic version of this will be a generator that yield its results, instead of collecting them in a list to return at the end, but this requires only minor changes (just yield instead of calling solutions.append ). Using a generator can also allow you to skip copying the board every time you have a solution, if you can depend on the consumer of the generator, using the result immediately (or making your own copy) before it starts the generator again.

Another idea is to simplify the presentation of your advice. You know that there can only be one queen in this row, so why not just keep the column where it was placed in the one-dimensional list (with the sentinel value, for example 1000 , indicating that the queen was not placed)? Thus, [1, 3, 0, 2] will be the solution to the problem with four queens, with queens in (0, 1) , (1, 3) , (2, 0) and (3, 2) (you can get these tuples using enumerate if you need them). This avoids the for loop during the backtracking phase and probably checks if the square is safe, since you do not need to look for a queen board.

Edit to ask additional questions:

At point Q1, you must deeply copy the board, because otherwise you will get a list of links to the same board. For comparison:

 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 with Q2, you need return stop the code from working. You can separate the return from the recursive call if you want to make it more clear that the return value does not matter:

 place_queen(board, row+1, 0) return 

Please note that your current code may work, but it does some dubious things. You call is_safe with row values ​​outside ( row == len(board) ), and this only happens because your implementation of is_safe reports them as unsafe (without failures), which you return accordingly. And when you are in the backtracking code at line 0 (at the very end of the run), you simply exit correctly because the for loop cannot find the value 1 in board[-1] (that is, the last line). I suggest refactoring your code a bit more so as not to rely on such quirks to work properly.

Answer 2

Use the power of Python! I suggest yield your solutions found instead of return them. Thus, you have created a generator for all solutions. To make a list of this, a fairly straightforward (then you really need it) designation

 [ solution for solution in solve(4) ] 

or simply

 list(solve(4)) 

EDIT:

In your case, solve() and place_queen() should have generators created. In solve() you have to do the last: return place_queen(board, 0, 0) . In this case, you return the generator. (You can also do for solution in place_queen(board, 0, 0): yield solution , but this will just pass the resulting values.)

In place_queen() instead of return values ​​such as 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)