I was attempting a recursive solution to the n queens problem. Please take a look at this code:
def solve(n,chess_arr,forbidden_cells=[]):
print("1.",n,chess_arr,forbidden_cells)
if n>(n*n)-len(forbidden_cells):
return False
elif n==1:
printchessboard(chess_arr)
return True
else:
for i in range(len(chess_arr)):
for j in range(len(chess_arr[i])):
print("2. ",n,(i,j),(i,j) not in forbidden_cells,forbidden_cells)
if (i,j) not in forbidden_cells:
chess_arr[i][j]=["Q"]
forbidden_row=i
forbidden_col=j
partial_forbidden_cells=create_partial_forbidden(n,chess_arr,forbidden_row,forbidden_col,forbidden_cells)
forbidden_cells.extend(partial_forbidden_cells)
if solve(n-1,chess_arr,forbidden_cells):
return True
else:
chess_arr[i][j]=[]
for partial in partial_forbidden_cells:
forbidden_cells.remove(partial)
return False
def create_partial_forbidden(n,chess_arr,forbidden_row,forbidden_col,forbidden_cells):
partial_forbidden_cells=[]
######################################### This block takes care of rows and columns #################################################
partial_forbidden_cells.extend([(forbidden_row+i,forbidden_col )\
for i in range(-n,n)\
if (forbidden_row+i>=0 and forbidden_row+i<n and\
(forbidden_row+i,forbidden_col) not in forbidden_cells )])
partial_forbidden_cells.extend([(forbidden_row,forbidden_col+i )\
for i in range(-n,n)\
if (forbidden_col+i>=0 and\
forbidden_col+i<n and i!=0 and\
(forbidden_row+i,forbidden_col) not in forbidden_cells )])
# i!=0 ensures that the place where the queen is located is not repeated again
######################################### This block takes care of the diagonals ###################################################
partial_forbidden_cells.extend([(forbidden_row+i,forbidden_col+i)\
for i in range(-n,n) \
if (forbidden_row+i>=0 and\
forbidden_row+i<n and forbidden_col+i>=0 and\
forbidden_col+i<n and i!=0 and\
(forbidden_row+i,forbidden_col) not in forbidden_cells )])
partial_forbidden_cells.extend([(forbidden_row-i,forbidden_col+i) \
for i in range(-n,n) \
if (forbidden_row-i>=0 and\
forbidden_row-i<n and forbidden_col+i>=0 and\
forbidden_col+i<n and i!=0 and\
(forbidden_row+i,forbidden_col) not in forbidden_cells )])
# i!=0 ensures that the place where the queen is located is not repeated again
#####################################################################################################################################
#print("forbidden cells are ", forbidden_cells)
return partial_forbidden_cells
I am facing a conceptual doubt here. While the first print statement always returns a non empty forbidden_cells list on several occasions but the second print statement always returns an empty list. I am at a loss why this is so? Could someone please explain.
My expectation: Since I am passing the forbidden_list as a parameter, I expect it to get updated with each iteration and at each iteration, I would like to be dealing with the most recent and updated forbidden_list.
A typical output is as follows:
1. 3 [[['Q'], [], [], []], [[], [], [], []], [[], [], [], []], [[], [], [], []]] [(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (0, 2), (0, 3), (1, 1), (2, 2), (3, 3)]
2. 4 (0, 1) True []
Thanks for the help!
There are the following issues in your code:
The base case should not be n == 1, but n == 0, as in solve the value of n represents how many queens you still have to place on the board, and you only want to cry victory when you have placed all queens. Otherwise you stop to soon, and will not have placed the last queen. But see also next point, as it affects this one as well:
n represents the size of the board, but in solve it also represents how many queens are left to place on the board. That means that in the recursive calls of solve, you don't have n anymore in the first meaning. Yet you use it in different places as if it represents the size of the board. For instance in this formula:
if n>(n*n)-len(forbidden_cells):
Here you mean that if the number of queens to place (n) is more than the total number of cells (n*n) minus the cells that are forbidden, that we should backtrack. As you can see there is a conflict here. n*n is not the size of the board, but a meaningless value (the number of queens still to place, ... squared).
This confusion also has a crippling effect on the executions of create_partial_forbidden, where range(-n,n) will eventually not cover the whole column or row.
To fix this I would suggest to keep n as meaning the size of the board, and instead give the first parameter of solve the name queens, so to make the distinction. Add a statement at the top of solve that sets a variable n to represent the size (width) of the board, as we don't need a parameter for that really:
n = len(chess_arr)
And then you need to carry that distinction through the rest of your code:
The backtracking check should be changed to:
if queens > n*n-len(forbidden_cells):
The base case check should be changed to:
elif queens==0:
The recursive call should pass queens-1 as first argument
In create_partial_forbidden you have a recurring error because you copied the following condition several times:
(forbidden_row+i,forbidden_col) not in forbidden_cells )
But this is only correct at its first occurrence. In the other three occurrences the +i should be adapted depending on the context (sometimes it should be added to the column, sometimes subtracted from the row...etc). Because of this bug, you'll return fewer forbidden cells than intended.
If you fix the above points it should work. A few more remarks:
I wouldn't assign lists to the cells of the chess board. That list wrapper doesn't serve a purpose. Just assign strings, like ="Q" instead of =["Q"] and ="" instead of =[]. You'll have to adapt your printchessboard function accordingly, but to me it makes more sense.
The function create_partial_forbidden doesn't use the chess_arr parameter, so I would just drop it.
Don't assign a default parameter value that is mutable. So forbidden_cells=[] is bad practice. The unintended effects of this has tricked many coders before you. Instead force the caller to provide the argument explicitly or provide None as default, but then you need to have a statement in your function that replaces that default with an empty list.
The printchessboard function could take forbidden_cells as extra argument so you can mark which cells are forbidden in the output. This can be useful for debugging.
Here is your code with the above points addressed, and with an example run for a standard chess board size (8):
# Added parameter for more clues in the output
def printchessboard(chess_arr, forbidden_cells):
for i, row in enumerate(chess_arr):
for j, cell in enumerate(row):
print("X" if (i, j) in forbidden_cells and cell == "." else cell, end=" ")
print()
print()
# Rename first parameter, remove mutable default value from last paramter
def solve(queens, chess_arr, forbidden_cells):
n = len(chess_arr) # Make distinction between queens and n.
# Corrected backtracking condition:
if queens > n*n-len(forbidden_cells):
return False
# Corrected base case condition
elif queens==0:
return True
else:
for i in range(len(chess_arr)):
for j in range(len(chess_arr[i])):
if (i,j) not in forbidden_cells:
chess_arr[i][j] = "Q" # not ["Q"]
forbidden_row = i
forbidden_col = j
# Drop the chess_arr argument:
partial_forbidden_cells = create_partial_forbidden(n,
forbidden_row, forbidden_col, forbidden_cells)
forbidden_cells.extend(partial_forbidden_cells)
# Pass queens-1 as argument
if solve(queens-1, chess_arr, forbidden_cells):
return True
else:
chess_arr[i][j] = "." # Not list, but string
for partial in partial_forbidden_cells:
forbidden_cells.remove(partial)
return False
# chess_arr parameter is not used
def create_partial_forbidden(n, forbidden_row, forbidden_col, forbidden_cells):
partial_forbidden_cells=[]
partial_forbidden_cells.extend([
(forbidden_row + i, forbidden_col)
for i in range(-n, n)
if forbidden_row + i >= 0 and forbidden_row + i < n and
(forbidden_row + i, forbidden_col) not in forbidden_cells
])
partial_forbidden_cells.extend([
(forbidden_row,forbidden_col + i)
for i in range(-n, n)
if (forbidden_col + i >= 0 and forbidden_col + i < n and i!=0 and
# correction of tuple, here and in the next blocks
(forbidden_row,forbidden_col+i) not in forbidden_cells)
])
partial_forbidden_cells.extend([
(forbidden_row + i, forbidden_col + i)
for i in range(-n, n)
if (forbidden_row + i >=0 and forbidden_row + i < n and
forbidden_col + i >=0 and forbidden_col + i < n and i!=0 and
(forbidden_row + i, forbidden_col + i) not in forbidden_cells)
])
partial_forbidden_cells.extend([
(forbidden_row - i,forbidden_col + i)
for i in range(-n, n)
if (forbidden_row - i >= 0 and forbidden_row - i < n and
forbidden_col + i >= 0 and forbidden_col + i < n and i!=0 and
(forbidden_row - i, forbidden_col + i) not in forbidden_cells)
])
return partial_forbidden_cells
def main():
n = 8
chess_arr = [
['.'] * n
for _ in range(n)
]
solve(n, chess_arr, [])
print("solution:")
printchessboard(chess_arr, [])
main()
There is still room for improvement:
forbidden_cells should better be a set than a list.
As you need to end up with one queen in each row, you'll get better efficiency if you have each call of solve consider placing a queen on a specific row only. If that is not possible, you can already backtrack.
There are greedy algorithms to solve this puzzle efficiently. See for instance Implementing a Python algorithm for solving the n-queens problem efficiently.