How this generator work? It obviously changed over during the outer for loop. Does the generator evaluate during the for loop?
The code is adapted from http://rosettacode.org/wiki/N-queens_problem#Python
If I import the code, it shows:
[[1, 3, 0, 2], [2, 0, 3, 1]]
Before the code it says:
"A surprisingly simple change to the above code (changing the list comprehension to a generator expression) produces a backtracking solution: "
class Solution:
# @return a list of lists of string
def under_attack(self, col, queens):
return col in queens or any(abs(col - x) == len(queens)-i for i,x in enumerate(queens))
def solve(self,n):
solutions = [[]]
for row in range(n):
solutions = (solution+[i] for solution in solutions
for i in range(n)
if not self.under_attack(i, solution))
print(list(solutions))
return solutions
A=Solution()
list(A.solve(4))
The algorithm works exactly the same way as the one using a list comprehension, the only difference really is that it uses a generator expression -- in fact, it creates a generator with more generators nested inside! So instead of listing all the possible solutions at once, it lazily generates more solutions as needed.
You can easily verify this by increasing some globally defined counter variable each time under_attack is called, and seeing how many times this counter has been increased.
gen = solve(8) # just create the generators, under_attack called 0 times
next(gen) # first solution, under_attack called 876 times
list(gen) # all remaining solutions, under_attack called 15720
If you do list(gen), it generates all the solutions, while next(gen) calculates just one.
Now for the actual algorithm. This is easier explained in the non-generator version. Also, no class needed.
def under_attack(col, queens):
return col in queens or any(abs(col - x) == len(queens)-i # (1)
for i,x in enumerate(queens)) # (2)
def solve(n):
solutions = [[]]
for row in range(n): # (3)
solutions = [solution+[i] for solution in solutions # (4)
for i in range(n) # (5)
if not under_attack(i, solution)] # (6)
print solutions # remove this when using generator! # (7)
return solutions
First, the under_attack function. Given a column for a queen and the columns of the already placed queens, this checks whether there is already a queen in the same column (1, before or), or whether any of the queens is on the same diagonal (2).
Now for solve: This loops over all the rows of the board, placing one queen in each row. solutions is a list of partial solutions, where each sub-list holds the columns of the queens placed so far. [[3,1]] would mean one (partial) solution with a queen in row 0, col 3, and one in row 1, col 1. Now, for each row (3), it updates the partial solutions with each combination of partial solution for the rows so-far (4) and column for the new queen (5) where that queen would not be under attack (6).
The reason I chose the non-generator version to explain was that this way we can print the partial solutions in each iterations of the loop (7). Using the generator this would not be possible, since just printing the list would exhaust the generator and there would be no more partial solutions to build upon. For n=4:
[[0], [1], [2], [3]] # 1st queen
[[0, 2], [0, 3], [1, 3], [2, 0], [3, 0], [3, 1]] # 2nd queen
[[0, 3, 1], [1, 3, 0], [2, 0, 3], [3, 0, 2]] # 3rd queen
[ [1, 3, 0, 2], [2, 0, 3, 1]] # 4th queen
The first queen can be placed in any of the columns. This already restricts the possible positions for the second queen, for which there are now only one or two possible places. The third queen is even more restricted, and for some positions of queen 1 and 2, no position can be found at all. Finally, the last queen is placed, and this is the solution set.