在python中，应用于共享数据类型的递归出错

Question

我曾尝试应用回溯法找出所有八个皇后难题的解决方案。 选择了三种不同的语言（c++、golang、python），并对每种语言应用了相同的OOP方法。 下面是使用c++的示例（为了简单易读，省略了析构函数和copy运算符），找出了92个结果案例：

#include <iostream>
#include <cstdlib>

class QueenBoard {
private:
    int m_size;
    int m_score;
    int **m_desk;

    bool tryQueen(int y, int x) const {
        for(int i = 0; i < y; i++) {
            if(m_desk[i][x] > 0) {
                return false;
            }
        }

        for(int i = 1; y-i >= 0 && x-i >= 0; i++) {
            if(m_desk[y-i][x-i] > 0) {
                return false;
            }
        }

        for(int i = 1; i <= y && x+i < m_size; i++) {
            if(m_desk[y-i][x+i] > 0) {
                return false;
            }
        }
        return true;
    }

    void putQueen(int y) {
        if(y == m_size) {
            show();
            std::cout << "Score: " << ++m_score << "\n\n";
            return;
        }

        for(int x = 0; x < m_size; x++) {
            if(tryQueen(y, x)) {
                m_desk[y][x] = 1;
                putQueen(y+1);
                m_desk[y][x] = 0;
            }
        }
    }

public:
    QueenBoard(int size)
        : m_size(size),
          m_score(0)
    {
        m_desk = new int*[size];
        for (int y = 0; y < size; y++) {
            m_desk[y] = new int[size];
            memset(m_desk[y], 0, size*sizeof(*m_desk[y]));
        }
    }

    ~QueenBoard() {
        for (int y = 0; y < m_size; y++) {
            delete m_desk[y];
        }
        delete m_desk;
    }

    void show() const {
        for(int y = 0; y < m_size; y++) {
            for(int x = 0; x < m_size; x++) {
                std::cout << ((m_desk[y][x]) > 0 ? "|Q" : "|.");
            }
            std::cout << "|\n";
        }
    }

    void matches() {
        putQueen(0);
        m_score = 0;
    }
};

int main()
{
    QueenBoard b(8);
    b.matches();
}

使用python的逻辑相同：

from __future__ import print_function


class QueenBoard(object):
    def __init__(self, size):
        self.size = size
        self.desk = [[0] * size] * size
        self.score = 0

    def __str__(self):
        s = ""
        for y in self.desk:
            for x in y:
                s = "%s|%c" % (s, "Q" if x else ".")
            else:
                s = "%s|\n" % s
        return s

    def _try_queen(self, y, x):
        i = 0
        while i < y:
            if self.desk[i][x] > 0:
                return False
            i = i+1
        i = 1
        while y-i >= 0 and x-i >= 0:
            if self.desk[y-i][x-i] > 0:
                return False
            i = i+1
        i = 1
        while y-i >= 0 and x+i < self.size:
            if self.desk[y-i][x+i] > 0:
                return False
            i = i+1
        return True

    def _put_queen(self, y):
        print(self)
        if y == self.size:
            self.score = self.score+1
            print(self)
            print("Score: %d\n" % self.score)
            return

        for x in range(0, self.size):
            if self._try_queen(y, x):
                self.desk[y][x] = 1
                self._put_queen(y+1)
                self.desk[y][x] = 0

    def matches(self):
        self._put_queen(0)
        self.score = 0


def main():
    b = QueenBoard(8)
    b.matches()


if __name__ == '__main__':
    main()

我尝试使用pdb找出根本原因，并简单地将断点放在\u put\u queen（）方法的开头。在第二次触发时，第一个垂直线完全填满，这是意外的原因：

|Q|.|.|.|.|.|.|.|
|Q|.|.|.|.|.|.|.|
|Q|.|.|.|.|.|.|.|
|Q|.|.|.|.|.|.|.|
|Q|.|.|.|.|.|.|.|
|Q|.|.|.|.|.|.|.|
|Q|.|.|.|.|.|.|.|
|Q|.|.|.|.|.|.|.|

期望值：

|Q|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|

我重写了结构化编程方式（摆脱了类），得到了和以前一样的结果

Answer 1

带符号

[[0] * size] * size

您正在制作同一阵列的3个副本：

[[0] * size] <  array copied _size_ times

而更正确的符号

[[0] * size for _ in range(size)]

指：

[ create an array of [[0] * size] * all places in the range 0 to size]

不是彼此的复制品