This is a solution for the n-queen question. In recursion calls, it passes modified lists. My question is for each recursion call, does it create three new lists: queens, xy_dif, xy_sum and keep them in the call stack? Or there are only those three lists, each recursive call just modified them in place? If that is the case, I don't understand how it solves the problem like below:
DFS([],[],[]) calls DFS([0], [0], [0]), then DFS([0], [0], [0]) calls DFS([0,2],[0,-1],[0,3]), it didn't pass the if condition so it returns.
Then the for loop continue, q=3, my question is why is DFS([0,3],[0,-2],[0,4]) the next call instead of DFS([0,2,3],[0,-1,-2],[0,3,4])?
How was those three lists reverted back to the state of original states after call DFS([0], [0], [0])?
def solveNQueens(self, n):
def DFS(queens, xy_dif, xy_sum):
print('call function DFS({},{},{})'.format(queens, xy_dif, xy_sum))
p = len(queens)
print('updated row p is ', p)
if p==n:
result.append(queens)
print('p==n, result is ', result)
return None
for q in range(n):
print('loop starts, q is ', q)
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
result = []
DFS([],[],[])
return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
Add some "standard" recursion tracking, and you can see the results easily. The id function is your friend in this case, showing whether a particular parameter refers to the same entity.
As you can see in the output below, each parameter has a unique id: it's an independent object. This is because you have not passed the parameters of one call to the next. Rather, you've created a temporary variable on the stack. If you simply pass through queens, for example, then that list reference is shared by all calls.
On the other hand, queens+[q] is not queens; rather, it is a new list expression: a temporary variable on the stack, with a separate value.
If you wished to share the structures, you would first alter queens, and then pass that altered version to the next level:
queens.append(q)
DFS(queens, xy_dif+[p-q], xy_sum+[p+q])
In this usage, xy_diff and xy_sum are still independent variables on each call, b ut queens is shared.
Your code with recursion instrumentation:
indent = ""
def DFS(queens, xy_dif, xy_sum):
global indent
print(indent, "ENTER DFS", queens, xy_dif, xy_sum)
print(indent, "parameter IDs:", id(queens), id(xy_dif), id(xy_sum))
indent += " "
print('call function DFS({},{},{})'.format(queens, xy_dif, xy_sum))
p = len(queens)
print('updated row p is ', p)
if p==n:
result.append(queens)
print('p==n, result is ', result)
indent = indent[2:]
return None
for q in range(n):
print('loop starts, q is ', q)
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
result = []
DFS([],[],[])
send_back = [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
print(indent, "LEAVE DFS", queens, xy_dif, xy_sum)
indent = indent[2:]
return send_back
Start of output:
ENTER DFS [] [] []
parameter IDs: 1813255818376 1813255818888 1813255819016
call function DFS([],[],[])
updated row p is 0
loop starts, q is 0
ENTER DFS [0] [0] [0]
parameter IDs: 1813255827784 1813258276680 1813255818760
call function DFS([0],[0],[0])
updated row p is 1
loop starts, q is 0
loop starts, q is 1
loop starts, q is 2
ENTER DFS [0, 2] [0, -1] [0, 3]
parameter IDs: 1813255817480 1813255817352 1813255817928
call function DFS([0, 2],[0, -1],[0, 3])
updated row p is 2
loop starts, q is 0
loop starts, q is 1
loop starts, q is 2
loop starts, q is 3
ENTER DFS [] [] []
parameter IDs: 1813255817864 1813255817736 1813255816712
call function DFS([],[],[])
updated row p is 0
loop starts, q is 0
ENTER DFS [0] [0] [0]
parameter IDs: 1813255816392 1813255816264 1813255816136
call function DFS([0],[0],[0])
...