Yielding from recursive helper function

Question

I want to yield the results from a recursive function (code below) but am having difficulties getting the output to match what I want. Ideally, if I call

print(list(n_queens_solutions(4)))

I would see

[[1, 3, 0, 2], [2, 0, 3, 1]]

but instead the function returns

[[], []]

I'm not too familiar with Python generators; I've tried various permutations of "yield" and "return" to no avail.

def n_queens_valid(board):
    for q1 in range(len(board)):
        for q2 in range (1, len(board)-q1):
            if board[q1] == board[q1+q2] or board[q1+q2] == board[q1]+q2 or board[q1+q2] == board[q1]-q2:
                return False
    return True

def n_queens_solutions(n):
    board = []
    return n_queens_helper(0, board, n)

def n_queens_helper(n, board, size):
    if len(board) == size:
        print(board)
        yield board
    else:
        for i in range(size):
            board.append(i)
            if n_queens_valid(board):
                yield from n_queens_helper(n+1, board, size)
            board.pop()

print(list(n_queens_solutions(4)))

The print from the last line in the code above should output: [[1, 3, 0, 2], [2, 0, 3, 1]], but instead returns [[], []].

Answer 1

Yes, you need to work through a tutorial on generators to understand more fully how they work. The problem you're facing at the moment is that n_queens_solutions calls the helper function only once -- that first branch fails to find a solution, and you're displaying the empty board returned upon failure.

Very briefly, think of a generator as a function with a bookmark. When you call the generator, it executes until it hits the first yield; it returns that value, but retains all of its state information: all variable values, its place in the code, etc. When you call it again, it restarts from that point and continues until it reaches the next yield, continuing in this fashion until it falls off the end of the code.

The simplest use of a generator is as a type of iterator:

for solution in n_queens_helper(...):

You've used it both this way (by building a list of solutions in your main program) and to recur on partial solutions (with yield from), but you need a little more work on the control flow. Try inserting a tracing statement:

def n_queens_helper(n, board, size):
    print("ENTER helper", n, board)
    if len(board) == size:

Watch the progression of execution now.

Answer 2

Let's illustrate what is happening with an simpler example:

def my_func():
  output = [1,2,3]
  print("Output", output)
  yield output
  print("Let's now clear the output")
  output.clear()
  print("Cleared output", output)

result = my_func()
print("Result", result)
print("Result List", list(result))

Output:

Result <generator object my_func at 0x7fd7ccc2a6d0>
Output [1, 2, 3]
Let's now clear the output
Cleared output []
Result List [[]]

• When the function itself it called (first line of the output), nothing in the generator function is actually executed.
• When we fetch all the content from the generator (by calling list(result)), we run the generator until it reaches the end of the function, putting all yield result in the list
• As we can see, because everything in the function is now executed, the output.clear() method is also executed.
• The content of the result variable matches the content of the output variable at the end of the generator function

To prevent this behaviour, one easy solution is to return a copy of the value we are returning, so we can manipulate it later: yield output[:] (this is a shallow copy, though)