I wrote Python code for the N-queen problem which prints each solution as it's found:
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)
How can I modify this code to return a list of all the solutions(board configurations) instead of printing them?
I tried it like so:
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 the solutions list only consists of one possible board configuration.
How can I make it build the entire list?
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.