Appending a global list to a global list?

Question

I have written following code for solving the n-Queens problem where we have to find all possible legal (non-attacking) placements of n queens in an n*n chessboard. The code uses the standard backtracking solution.

Here the method n_queens uses the helper method solve_n_queens which uses recursion. The outer method just initializes global lists result & col_placement and calls the helper method.

def n_queens(n):
    def solve_n_queens(row):
        if row == n: # all queens are legally placed
            result.append(list(col_placement))
            return
        for col in range(n):
            # check if new queen is either 1) in same column or 2) same diagonal with any previously placed queen
            if all(abs(col-c) not in (0, row-r) 
                   for r, c in enumerate(col_placement[:row])):
                col_placement[row] = col
                solve_n_queens(row+1)
    result, col_placement = [], [0] * n # result is empty initially; [0] * n means no queen is placed
    solve_n_queens(0)
    return result

This gives erroneous output for n_queens(4)

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

However it is not an algorithmic bug because just altering the 4th line result.append(col_placement) to result.append(list(col_placement)) mysteriously gives the correct output

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

What I don't grok is when col_placement is already a list, why do we need to call the list method?

This is a variant of [List of lists changes reflected across sublists unexpectedly](https://stackoverflow.com/q/240178/364696); you're not using sequence multiplication, but the effect of appending the same name to the `list` multiple times without copying it or rebinding the name between appends is the same. — ShadowRanger, May 02 '18 at 02:24

Julien · Answer 1 · 2018-05-02T01:55:43.447

The problem is that without using list you are appending a reference to the same and only list col_placement you are working with (as you can see the results are not only wrong, but they are also the same). Using list creates a new copy (a instant snapshot of col_placement) that will not be modified when col_placement does as you keep going through the rest of the program.

So essentially list(col_placement) is the same as col_placement.copy() or col_placement[:].

Appending a global list to a global list?

1 Answers1