关于全局列表追加到全局列表的疑问及n皇后回溯代码问题

Hey there! Let's break down how to correctly append your column placement list to the result list for the n-Queens problem, plus key things to watch out for in this scenario.

Correct Way to Append the List #

The critical mistake to avoid here is appending the original list object directly. Since lists are mutable in Python, if you just do result.append(col_placement), every entry in result will be a reference to the same col_placement list. As your backtracking code modifies this list (via append/pop), all entries in result will end up reflecting the final state of col_placement (usually empty or the last partial solution) instead of the unique valid configurations.

Instead, you need to append a copy of col_placement when you hit the base case (all queens placed). Here's how to adjust your code:

def n_queens(n):
    result = []
    col_placement = []  # Tracks column index for each row (index = row, value = column)

    def solve_n_queens(row):
        if row == n:
            # Append a copy of the current placement state
            result.append(col_placement.copy())  # Or list(col_placement), or col_placement[:]
            return
        
        for col in range(n):
            if is_valid(row, col):
                col_placement.append(col)
                solve_n_queens(row + 1)
                col_placement.pop()  # Backtrack: undo the current column choice

    def is_valid(row, col):
        # Check if placing a queen at (row, col) conflicts with existing queens
        for r in range(row):
            # Same column, or same diagonal (absolute difference of rows = absolute difference of columns)
            if col_placement[r] == col or abs(col_placement[r] - col) == abs(r - row):
                return False
        return True

    solve_n_queens(0)
    return result

Key Considerations for This Scenario #

• Mutable Object Reference Pitfall: This is the biggest gotcha. Always remember that mutable types (like lists) are passed by reference. Without creating a copy, all entries in result will point to the same underlying list, which gets modified during backtracking.
• Closure Variable Scope: Your result and col_placement variables are defined in the outer n_queens function, making them closure variables for solve_n_queens. Since we're only modifying the contents of these lists (not reassigning them), we don't need the nonlocal keyword. If you tried to reassign them (e.g., result = [] inside solve_n_queens), you'd need to declare them as nonlocal to avoid creating local variables.
• Proper Backtracking: Make sure you always call col_placement.pop() after the recursive call. This undoes the current column choice, allowing the loop to try the next valid column for the current row. Skipping this step will leave invalid entries in col_placement and break subsequent recursive calls.
• Performance of Copies: For large values of n, creating a copy of col_placement each time you find a valid solution adds a small overhead. However, this is unavoidable—since the n-Queens problem's solution count grows exponentially with n, the overhead is negligible compared to the recursive work itself.

内容的提问来源于stack exchange，提问作者kamalbanga