python - 计算 N Queens 函数产生的解的数量。

Question

我编写了一个函数，可以生成 N 皇后问题的所有可能解决方案。它需要用户输入一个整数，即表格的尺寸。即，如果用户输入 4，那么它将列出 4x4 表的所有可能解决方案。当输入 n=4 时，输出如下所示:

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

这是我使用的功能:

def nQueens(partialSolution, n):
    allPositions = getPositions(partialSolution, n)
    if len(partialSolution) == n:
        print(partialSolution)
    else:
        for item in allPositions: 
            partialSolution.append(item)
            nQueens(partialSolution, n)
            partialSolution.pop()
nQueens([], n)

在此函数中的某个位置，我需要实现一个计数变量，该变量最后将输出解决方案的数量。例如，如果输入4，那么它将输出2，因为有两种解决方案:

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

我尝试了以下方法，但没有成功:

count = 0
for i in partialSolution:
    count+=1
print(count)

因为它不在函数本身内，所以我收到一条错误消息，指出partialSolution 未定义。我不确定如何在函数本身中实现这样的东西。

Answer 1

假设您的代码是正确的，您可以尝试返回函数的计数，基本情况是它实际打印解决方案时，如下所示(小心，未经测试的代码):

def nQueens(partialSolution, n):
    allPositions = getPositions(partialSolution, n)
    if len(partialSolution) == n:
        print(partialSolution)
        return 1
    else:
        ctr = 0
        for item in allPositions: 
            partialSolution.append(item)
            ctr += nQueens(partialSolution, n)
            partialSolution.pop()

        return ctr

基本情况返回一个，因为它打印一个有效的解决方案，然后，在执行递归调用之后，在进入递归的下一个分支之前，对到目前为止找到的解决方案的数量进行求和。