python-constraint 无法解决 n 皇后难题

Question

我正在使用

python-constraint

库来尝试解决 n 皇后问题 （n 个皇后被放置在 n×n 的棋盘上，并且它们的排列方式必须确保它们不会互相威胁）

我的表述是这样的：

from constraint import *

n = 8
problem = Problem()
problem.addVariables(range(n),range(n))

for i in range(n):
  for j in range(i):
    problem.addConstraint(lambda a,b:a!=b,(i,j))
    problem.addConstraint(lambda a,b:abs(a-b)!=abs(i-j),(i,j))

但是，当我尝试使用

problem.getSolution()

获得解决方案时，我只是得到

None

。我做错了什么？

Answer 1

生成的 lambda 的非常经典的错误（与约束无关）。

考虑这段代码

ll=[]
for i in range(3):
    l=lambda: print("i=", i)
    ll.append(l)

ll[0]()
ll[1]()
ll[2]()

它不会像您预期的那样显示 0、1、2。 显示 2, 2, 2。

这 3 个（不同的）函数都做同样的事情：它们显示 i 值。但如果

ll[0]

、

ll[1]

、

ll[2]

确实是 3 个不同的函数，那么仍然只有一个

i

。当然，当您创建

0

时，我的值是

ll[0]

。但是

ll[0]

的工作是显示

i

，而不是显示

i

曾经在创建

ll[0]

时所具有的值。

有几种方法可以强制评估

i

在那一刻

一个可能是

ll=[]
for i in range(3):
   (lambda i: ll.append(lambda: print("i=", i)))(i)
ll[0]()
ll[1]()
ll[2]()

本次显示为0、1、2。 因为

ll[0]

的作用就是显示

i

。但这次 i 不是 for 循环的（唯一）计数器。

i

是被调用的 lambda 的参数。调用该 lambda（

lambda i:...

函数，而不是在其中创建的函数）时，它们的数量与数量一样多。

相同代码的更清晰（但更长）的版本将是

ll=[]

def createAndAddLambdaToLL(x):
    l=lambda: print("x=", x)
    ll.append(l)

for i in range(3):
    createAndAddLambdaToLL(i)

ll[0]()
ll[1]()
ll[2]()

createAndAddLambdaToLL

是我之前代码的外部 lambda。 请注意，我还重命名了参数

x

，以明确打印的不是

i

（

i

，在

ll[?]()

调用时，所有这些都将是 2），但它打印出来的是

x

。并且有 3 个不同的

x

，是在调用

createAndAddLambdaToLL

时创建的。

回到你的问题

from constraint import *

n = 8
problem = Problem()
problem.addVariables(range(n),range(n))

def addConstraintDiag(i,j):
    problem.addConstraint(lambda a,b: abs(a-b)!=abs(i-j), (i,j))

for i in range(n):
    for j in range(i):
        problem.addConstraint(lambda a,b:a!=b,(i,j))
        addConstraintDiag(i,j)

print(problem.getSolutions())

请注意，第一个约束（不共享行）不是问题，因为

lambda a,b:a!=b

不依赖于

i

和

j

（事实上，它是同一个函数的 28 倍。您可以创建一次全部在循环之外，并将其添加为约束 28 次，但重点是，该函数不需要其

i

和

j

都是 28 种组合，因为它甚至不使用。

i

和

j

。约束本身可以，但 lambda 不可以。

不过，为了安全起见，您可以在函数

addConstraints

中添加 2 个约束，而不必费力思考是否需要对

i

和

j

进行部分评估。