N-Queens Symmetry打破谷歌OR工具

Question

Google或-tools的一个示例是n-queens问题的解算器. 在底部,它表示可以通过向约束求解器添加对称破坏约束来改进实现.

环顾互联网,我发现n-queens问题的对称性破坏约束,但我不能为我的生活弄清楚如何将这些转换为约束到实现它们的python代码.

---

编辑:这是一个糟糕的问题,让我们更新......

我试过了什么？

以下是上面第一个链接的设置:

from ortools.constraint_solver import pywrapcp

N = 8
solver = pywrapcp.Solver("n-queens")
# Creates the variables.
# The array index is the column, and the value is the row.
queens = [solver.IntVar(0, N - 1, "x%i" % i) for i in range(N)]
# Creates the constraints.
# All rows must be different.
solver.Add(solver.AllDifferent(queens))
# All columns must be different because the indices of queens are all different.
# No two queens can be on the same diagonal.
solver.Add(solver.AllDifferent([queens[i] + i for i in range(N)]))
solver.Add(solver.AllDifferent([queens[i] - i for i in range(N)]))

# TODO: add symmetry breaking constraints

db = solver.Phase(queens, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)
solver.NewSearch(db)
num_solutions = 0
while solver.NextSolution():
  num_solutions += 1
solver.EndSearch()
print()
print("Solutions found:", num_solutions)
print("Time:", solver.WallTime(), "ms")

我知道我可以成功实现简单的约束.如果我想确保解决方案总是在第一行的第一列中有一个女王,我可以像这样实现:

solver.Add(queens[0] == 0)

该queens[0]变量表示第一列中的皇后位置,并且仅当第一列在第一行中具有皇后时才满足此约束.这当然不是我想要做的,因为解决方案可能不包括任何角落单元.

对于n皇后问题的对称性破坏约束如下.它们直接从第二段中的链接中提取.

我理解这些约束是如何工作的.这个想法是你可以将这个函数应用到n-queens板上的每个单元格,以便将状态转换为等效状态.其中一种状态将是该州的规范表示.这用作通过消除重复评估来修剪未来处理的方法.

如果我只是按照事实的方式实现这个,我会完全按照上面描述的那样,使用每个可能的对称破坏函数转换状态,计算某种状态散列(例如每列中所选行的字符串)并选择每个建议解决方案中最低的那个.跳过我们之前见过的未来处理.

我的问题是我不知道如何将这些转换转换为谷歌或工具约束编程求解器的约束.

让我们来看看最简单的一个,d1(r[i] = j) => r[j] = i关于主对角线的反思.我所知道的是,转换需要应用于所有单元格,然后与当前状态进行比较,以防止扩展.我不太了解python来理解这里的变换是什么类型的表达式,我只是无法弄清楚如何创建将变换与此特定求解器的当前状态进行比较的约束.

state = [queens[i].Value() for i in range(N)]
symX    = [state[N - (i + 1)] for i in range(N)]
symY    = [N - (state[i] + 1) for i in range(N)]
symD1   = [state.index(i) for i in range(N)]
symD2   = [N - (state.index(N-(i+1)) + 1) for i in range(N)]
symR90  = [N - (state.index(i) + 1) for i in range(N)]
symR180 = [N - (state[N-(i+1)] + 1) for i in range(N)]
symR270 = [state.index(N-(i+1)) for i in range(N)]

Answer 1

您必须使用所寻求的解决方案之间已知的对称关系来识别将消除等效解决方案的约束。

1. 对于每个 的解queens[0] >= N/2，都有另一个垂直镜像的解queens[0] <= N/2。因此，我们可以寻找 的值较小的解queens[0]，并添加以下约束：

   solver.Add(queens[0] < (N+1)//2) # Handle both even and odd values of N
   

2. 然后，满足条件的解queens[0] < queens[N-1]具有满足 的等价水平镜像解queens[0] > queens[N-1]。您可以告诉求解器仅查找最左列中的皇后位于最右列中的皇后下方的那些解：

   solver.Add(queens[0] < queens[N-1])
   

我无法轻易地制定反映旋转对称性的约束，但我相信这是可能的。