python - N 皇后区对称性破坏 Google OR 工具

Question

One of the samples for the Google or-tools is a solver for the n-queens problem.在底部，它表示可以通过向约束求解器添加对称破坏约束来改进实现。

环顾互联网，I found the symmetry breaking constraints for the n-queens problem ，但我终究无法弄清楚如何将这些约束转换为实现它们的 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 皇后板上的每个单元格，以便将状态转换为等效状态。这些状态之一将是该状态的规范表示。这被用作通过消除重复评估来修剪 future 处理的方法。

如果我只是以事后的方式实现它，我会完全按照我上面描述的那样做，使用每个可能的对称破坏函数转换状态，计算某种状态哈希(例如，所选行的字符串每列)并为每个建议的解决方案选择最低的一个。跳过我们之前看到的 future 处理。

我的问题是我不知道如何将这些转换转换为 google or-tools 约束规划求解器的约束。

我们来看最简单的，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

我尝试使用自定义 DecisionBuilder 将对称性用作新约束来修剪搜索树，但我无法使其工作。

相反，我不得不使用 SearchMonitor 来捕获每个解决方案的事件，并检查该解决方案是否与前一个解决方案对称。

我在这里添加了 SearchMonitor 的代码，覆盖“AcceptSolution”函数的解决方案捕获，以及用于计算和检查所有可能对称性的 gen_symetries 函数。

    class SearchMonitor(pywrapcp.SearchMonitor):
    def __init__(self, solver, q):
        pywrapcp.SearchMonitor.__init__(self, solver)
        self.q = q
        self.all_solutions = []
        self.unique_solutions = []
        self.n = len(self.q)

    def AcceptSolution(self):
        qval = [self.q[i].Value() for i in range(self.n)]
        self.all_solutions.append(qval)

        symmetries = [vv in self.unique_solutions for vv in gen_symmetries(self.n, qval)]

        if sum(symmetries) == 0:
            self.unique_solutions.append(qval)

        return False

def gen_symmetries(n, solution):
    symmetries = []

    #x(r[i]=j) → r[n−i+1]=j
    x = list(range(n))
    for index in range(n):
        x[n - 1 - index] = solution[index]

    symmetries.append(x)

    #y(r[i]=j) → r[i]=n−j+1
    y = list(range(n))
    for index in range(n):
        y[index] = (n - 1 - solution[index])

    symmetries.append(y)

    #d1(r[i]=j) → r[j]=i
    d1 = list(range(n))
    for index in range(n):
        d1[solution[index]] = index

    symmetries.append(d1)

    # d2(r[i]=j) → r[n−j+1]=n−i+1
    d2 = list(range(n))
    for index in range(n):
        d2[n - 1 - solution[index]] = (n - 1 - index)

    symmetries.append(d2)

    # r90(r[i]=j) → r[j] = n−i+1
    r90 = list(range(n))
    for index in range(n):
        r90[solution[index]] = (n - 1 - index)

    symmetries.append(r90)

    # r180(r[i]=j) → r[n−i+1]=n−j+1
    r180 = list(range(n))
    for index in range(n):
        r180[n - 1 - index] = (n - 1 - solution[index])

    symmetries.append(r180)

    # r270(r[i]=j) → r[n−j+1]=i
    r270 = list(range(n))
    for index in range(n):
        r270[n - 1 - solution[index]] = index

    symmetries.append(r270)

    return symmetries

稍后您只需像这样将监视器添加到您的求解器。

monitor = SearchMonitor(solver, queens)
solver.Solve(db, monitor)
solver.NewSearch(db)

最后只打印所有独特的解决方案

print("Unique Solutions:", len(monitor.unique_solutions), monitor.unique_solutions)

您可以在要点中看到完整的工作示例。

https://gist.github.com/carlgira/7a4e6cf0f7b7412762171015917bccb4