Maximus S - 1 year ago 78

Python 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`

`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)

- Why do we need to ? In other words, what exactly is happening when we do
`solutions.append(deepcopy(board))`

and why does this lead to appending the initial board which is`solutions.append(board)`

?`[[0,0,0,0] ...]`

- Why do we run into a problem when is replaced by
`return place_queen(board, row+1, 0)`

? We are not actually returning anything (or`place_queen(board, row+1, 0)`

), but without`None`

the list goes out of index.`return`

Answer Source

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 `yield`

s 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.