CODEWITHSUNDEEP
pythonrecursionreturn
Malafat
Malafat

Reputation: 21

What exactly does this return statement instruct the program to do?

Here is a recursive solution the 8 queens problem from https://wiki.python.org/moin/SimplePrograms . I am having difficulty in understanding how/why the return statement in the solve function works. At first glance, it looks like it breaks rules (like, solutions hasn't been declared or assigened value before the loop in the return statement, but it appears before the loop in the return statement) but I can run this successfully so I am curious to understand how it works and why someone may have chosen to write it this way (to be confusing? short? because of other restrictions I do not yet understand?)

BOARD_SIZE = 8

def under_attack(col, queens):
    left = right = col

    for r, c in reversed(queens):
        left, right = left - 1, right + 1

        if c in (left, col, right):
            return True
    return False

def solve(n):
    if n == 0:
        return [[]]

    smaller_solutions = solve(n - 1)

    return [solution+[(n,i+1)]
        for i in xrange(BOARD_SIZE)
            for solution in smaller_solutions
                if not under_attack(i+1, solution)]
for answer in solve(BOARD_SIZE):
    print answer

I am familiar with recursive solutions to problems from some experimentation and a course I've taken, but I am pretty new to python as a whole (I mostly have used java and C in classes and on my own).

Does anyone have a good way to explain how this syntax works or maybe other examples I can study that might help me make sense of it? This has really itched my curiosity...

Upvotes: 2

Views: 155

Answers (2)

Burhan Khalid
Burhan Khalid

Reputation: 174662

I guess your confusion is of this line of code:

       v---- this starts the list
return [solution+[(n,i+1)]
        for i in xrange(BOARD_SIZE)
            for solution in smaller_solutions
                if not under_attack(i+1, solution)]
                                                  ^-- this ends the list

This is actually a list comprehension, a short hand way to create lists.

Here is the longhand version of that loop.

x = []
for i in xrange(BOARD_SIZE):
    for solution in smaller_solutions:
        if not under_attack(i+1, solution):
            x.append(solution+[(n, i+1)])
return x

Upvotes: 5

Noctua
Noctua

Reputation: 5218

You are asking about list comprehensions. It's Python's way to do the functional maps (applying a function to each element of a list) and filters (filtering lists on certain conditions).

The easiest way to explain this would be with some examples.

Say:

>>> l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> [2 * i for i in l]
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
>>> [i for i in l if i > 5]
[6, 7, 8, 9, 10]

Now these can be combined, and you can use any number of for's:

>>> # squares of even numbers below 10
>>> [i * i for i in range(10) if i%2 == 0]
[0, 4, 16, 36, 64]
>>> # concatenating all lists
>>> ll = [[1, 2], [3, 4], [5, 6], [7, 8], [8, 10]]
>>> [i for l in ll for i in l]
[1, 2, 3, 4, 5, 6, 7, 8, 8, 10]

Upvotes: 3

Related Questions