8

Google or-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-queens 问题的对称破缺约束如下所示。它们是直接从第二段中的链接中提取的。

n-皇后对称破缺约束

我了解这些约束是如何工作的。这个想法是，您可以将此函数应用于 n-queens 板上的每个单元格，以便将状态转换为等效状态。这些状态之一将是该状态的规范表示。这被用作通过消除重复评估来修剪未来处理的方法。

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

我的问题是我不知道如何将这些转换转换为 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)]
4

2 回答 2

2

我尝试使用自定义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)

您可以在 gist 中查看完整的工作示例。

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

于 2017-09-22T17:34:47.913 回答
0

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

  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])

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

于 2016-12-20T19:14:08.320 回答