ORTools和Python中的NoCycle约束

Question

我正在用Python中的OR工具实现Knight-Tour问题，我正在努力解决无循环约束。在C++中，存在^ {< CD1> }全局约束，并且我假设在Python包装器中，与此等价的是^ {< CD2> }约束。在

到目前为止，我得到的简化代码（我从一些失败的示例中复制了TreeNoCycle部分）：

# side length of board
n = 5

# where the knight jumps to from field i, starting at 0, ending at n*n
jump_to = [solver.IntVar(1, n*n) for i in range(n*n)]

# snip other constraints

# the no cycle constraint
active = [solver.IntVar(1, 1) for i in range(dim * dim)]
for t in active:
    solver.Add(t == 1)
solver.Add(solver.TreeNoCycle(jump_to, active, lambda: None))

执行时，最后一个部分会出现以下错误：

python3.6/site-packages/ortools/constraint_solver/pywrapcp.py", line 337, in NextSolution return _pywrapcp.Solver_NextSolution(self) SystemError: returned a result with an error set

我的其余代码可以工作，也就是说，当我省略带有TreeNoCycle约束的部分时，我得到了许多解决方案，但有些解决方案带有断开的图。在

我的假设是正确的，TreeNoCycle是MakeNoCycle的Python方法吗？如果是，如何正确使用TreeNoCycle？如果。如果我不能使用TreeNoCycle，有什么想法可以用不同的方式实现呢？在

Answer 1

请使用CP-SAT解算器。在

请注意，在这种情况下，建模应该有点不同，因为电路约束采用一个标有布尔文字（布尔变量或其负）的图形。 您不需要整数变量。在

一些文档：

https://github.com/google/or-tools/tree/stable/ortools/sat/doc

https://developers.google.com/optimization/cp/cp_solver#cp-sat_example

和python示例（查找_星期六.py后缀）：

https://github.com/google/or-tools/tree/stable/examples/python