Python 列表和字典被覆盖或损坏？

Question

我正在尝试暴力解决 N 皇后国际象棋问题 https://en.wikipedia.org/wiki/Eight_queens_puzzle

我的代码可以正常工作，但是当我尝试 return 解决方案数据结构时出现异常行为。

包含解决方案的列表在某些时候被覆盖或损坏。

我试过使用多种不同的数据结构列表、字典、集合，结果都一样。

输出应该是

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

但目前return正在

[[3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3]]

import numpy as np

# Validation Functions
def checkRows(state):
    """
    Check only 1 queen per row
    """     
    for row in state:        
        if sum(row) > 1:
            return False
    return True

def checkCols(state):
    """
    Check only 1 queen exists in a column
    """
    for i in range(0,len(state)):
        count = 0
        for j in range(0,len(state)):            
            #print(state[j][i])
            count = count + state[j][i]
        if count > 1: return False
    return True   
    
def checkDiag(state):
    """
    Checks only 1 queen exists per diagonal
    
    """
    # Alter dimensions as needed
    n = len(state)
    x,y = n,n
    # incoming state list    
    a = np.array(state)
    diags = [a[::-1,:].diagonal(i) for i in range(-a.shape[0]+1,a.shape[1])]    
    diags.extend(a.diagonal(i) for i in range(a.shape[1]-1,-a.shape[0],-1))
    for n in diags:
        if sum(n) > 1: #if any of the diagonals sums to more than 1 there must be more than 1 queen in that diagonal
            return False
    return True
        
def checkState(state):
    """
    Returns false on one or more failures
    """
    return checkRows(state) and checkCols(state) and checkDiag(state)
    
def worker_translate(dim, sol):
    """
    Translate from the permutations function to a format to be checked by validation functions
    """
    state = []
    for val in range(dim - 1, -1, -1):
        inner_list = []
        for y in sol:            
            if y == val:
                inner_list.append(1)                                
            else:
                inner_list.append(0)  
        state.append(inner_list)
    return state

def print_solution(dim, sol):
    for val in range(dim - 1, -1, -1):
        for y in sol:
            if y == val:
                print('Q ', end='')
            else:
                print('. ', end='')
        print()
    print()


def runner(x):
    # go through the permutations searching for all possible solutions
    dim = int(x)    
    
    # populate this_permutation
    this_permutation = []
    for n in range(dim):
        this_permutation.append(0)

    # calculate the number of permutations
    possible_permutations = dim**dim
#     for n in range(dim):
#         possible_permutations *= dim
        
    mydict = {}
    mylist = []
    # iterate through all possible permutations    
    for n in range(possible_permutations):
        rem = n
        for m in range(dim):
            this_permutation[m] = rem % dim
            rem //= dim

            res = checkState(worker_translate(dim, this_permutation))
            if res:
                #print("Solution Found")
                #print(this_permutation)
                #print(worker_translate(dim, this_permutation))
                #print_solution(dim, this_permutation)
                mylist.append(this_permutation)
                mydict[n] = this_permutation
                print(mydict)
                print(mylist)
    print("data structures not working after this point")
    print(mydict)
    print(mylist)
    return(mydict,mylist)

print(runner(4))

编译代码的输出

{114: [2, 0, 3, 1]}
[[2, 0, 3, 1]]
{114: [2, 0, 3, 1]}
[[2, 0, 3, 1], [2, 0, 3, 1]]
{114: [2, 0, 3, 1]}
[[2, 0, 3, 1], [2, 0, 3, 1], [2, 0, 3, 1]]
{114: [2, 0, 3, 1]}
[[2, 0, 3, 1], [2, 0, 3, 1], [2, 0, 3, 1], [2, 0, 3, 1]]
{114: [1, 3, 0, 2], 141: [1, 3, 0, 2]}
[[1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2]]
{114: [1, 3, 0, 2], 141: [1, 3, 0, 2]}
[[1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2]]
{114: [1, 3, 0, 2], 141: [1, 3, 0, 2]}
[[1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2]]
{114: [1, 3, 0, 2], 141: [1, 3, 0, 2]}
[[1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2]]
data structures not working after this point
{114: [3, 3, 3, 3], 141: [3, 3, 3, 3]}
[[3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3]]
({114: [3, 3, 3, 3], 141: [3, 3, 3, 3]}, [[3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3]])

Process finished with exit code 0

Answer 1

请参阅评论中 Collin Heist 的回答以获取解释。

mylist.append(this_permutation.copy())

Python 列表和字典被覆盖或损坏？

Python List and Dictionary being overwritten or corrupted?

python

list

n-queens

python-3.x