OR-Tools 和 Python 中的 NoCycle 约束

Question

我正在 Python 中使用 OR-Tools 实现 Knight Tour Problem，我正在努力解决 No-Cycle 约束。在 C++ 中，有 MakeNoCycle 全局约束，我假设在 Python 包装器中，等效于 TreeNoCycle 约束。

我目前的简化代码（我从一些错误的例子中复制了 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例子（寻找_sat.py后缀）：

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

OR-Tools 和 Python 中的 NoCycle 约束

NoCycle constraint in OR-Tools and Python

python

or-tools