Python list is not passing as expected while doing recursion

Question

I'm trying to solve theN-Queues as following:

class Solution(object):
    def __init__(self):
        self.queues = []

    def DFS(self, n, row, col, pie, na, path):
        if row == n:
            print 'current recursion path: ', path
            self.queues.append(path)
            print 'paths within the recursion: ', self.queues
            return 

        for c in range(n):
            if (c not in col) and (c + row not in pie) and (row-c not in na):
                col.add(c)
                pie.add(c+row)
                na.add(row-c)
                # self.queues.append(c)
                # path += str(c)
                path.append(c)
                # print 'row: ', row, 'col: ', c, path
                self.DFS(n, row + 1, col, pie, na, path)
                col.remove(c)
                pie.remove(c+row)
                na.remove(row-c)
                # path = path[:-1]
                path.pop()
            # else:
                # path.pop()
        return None
        # print '\n'

    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        col = set()
        pie = set()
        na = set()
        print 'before recursion: ', self.queues
        self.DFS(n, 0, col, pie, na, [])
        print 'after recursion: ', self.queues
        # return self.reslutPrint(n)

I got the following print out:

before recursion:  []
current recursion path:  [1, 3, 0, 2]
paths within the recursion:  [[1, 3, 0, 2]]
current recursion path:  [2, 0, 3, 1]
paths within the recursion:  [[2, 0, 3, 1], [2, 0, 3, 1]]
after recursion:  [[], []]

As you can see, the recursion is getting the correct answer for each path, however, the answer is not appended to the global variable self.queues correctly. Can you please let me know why is this happening?

I'm guessing this is due to that when I appended the list to self.queues, it's giving the address instead of the actual value to self.queues. If so, how can I fix this?

Thanks a lot.

Ian

Answer 1

The problem you're having isn't with self.queues, but rather how you're handling path. When you pass path it into a function, you're passing it by assignment, not its value.

Therefore, when you add path to self.queues and later do path.pop(), it is affecting anywhere path is referenced, including in self.queues.

Here's a simple example of the problem:

>>> a = []
>>> b = [1, 2, 3]
>>> a.append(b)
>>> b.pop()
>>> print(a)
[[1, 2]]

So, what's the best way to correct this? You could, as others have suggested, copy your list before appending it, with self.queues.append(path[:]). But I think a closer examination suggests another answer: pass a new path to each new level of the recursion. Rather than path.append(c), try self.DFS(n, row + 1, pie, na, path + [c]. In this way, you're taking a more functional approach of immutability (you could go one step further and enforce immutability by using an immutable data structure, such as tuple). Here's how your code would look with this approach:

def DFS(self, n, row, col, pie, na, path):
    if row == n:
        print 'current recursion path: ', path
        self.queues.append(path)
        print 'paths within the recursion: ', self.queues
        return 

    for c in range(n):
        if (c not in col) and (c + row not in pie) and (row-c not in na):
            col.add(c)
            pie.add(c+row)
            na.add(row-c)
            self.DFS(n, row + 1, col, pie, na, path + [c])
            col.remove(c)
            pie.remove(c+row)
            na.remove(row-c)

Answer 2

You're right, when you append you are putting a list into self.queues, it's via the address. But that's not the issue, the issue is you later go on to modify that same object, and so emptying it also means self.queues holds a pointer to an empty list.

You need to make a copy of the path (eg by self.queues.append(path[:]) variable, and append that to queues. Or in the general case you can use python's copy moduele (either shallow or deep copy depending on your use case https://docs.python.org/2/library/copy.html)