n 车完成拼图的快速算法

Question

我受到这篇文章的激励，n-queens-completion 的复杂性。我对棋盘上非攻击车的完成问题感兴趣。

输入： 给定一个大小为 𝑛×𝑛 的棋盘，其中 𝑛−𝑘 车放置在非攻击位置，并且某些棋盘对角线由多组整数 𝐷 = { 𝑗₁, 𝑗₂, 表示。 .., 𝑗_𝑘 }

输出： 我们可以放置额外的 𝑘 车，这样所有 𝑛 车都不会攻击，并且每个新车都恰好放置在 𝐷 中的一条对角线上吗？

我怀疑这个问题是NP完全问题。有没有高效（快速）的算法？

Answer 1

这是一个约束满足问题，更具体地说是一个SAT问题，其中每个布尔变量对应于棋盘上的一个方块，指示它是否得到车。

约束表示每个未占用的行必须恰好有一个车，类似地每个未占用的列必须恰好有一个车。给定的对角线必须具有为其指定的车数。约束只需要参考位于至少一个给定对角线上的方格，并且不在已经有车的行/列上。其他方格可以忽略，因为很明显他们不会得到车。

有几个 Python 包可以解决此类问题，例如 scipy、numpy 等。这里我将使用 python-constraint 包。

from constraint import Problem, ExactSumConstraint
from collections import Counter

# rooks = list of coordinates of pre-placed rooks
# plusdiags = list of diagonals identified by row+col
# mindiags = list of diagonals identified by row-col
# The diagonal lists can have duplicates. Each given diagonal will get exactly
#    one new rook (not counting pre-placed rooks)
# Note that the size of the chess board is implied by the above input
# Returns a list of all rooks, including the pre-placed rooks, None if no solution

def solve(rooks, plusdiags, mindiags):
    n = len(rooks) + len(plusdiags) + len(mindiags)
    rows = set(range(n)).difference(row for row, col in rooks)
    cols = set(range(n)).difference(col for row, col in rooks)
    pluscounter = Counter(plusdiags)
    mincounter = Counter(mindiags)

    # cells that might receive a rook:
    #   ...are on rows and cols that don't have a rook yet, and
    #   ...are on one of the given diagonals
    cells = {
        (row, col) 
        for col in cols
        for row in rows
        if row + col in pluscounter or row - col in mincounter
    }
    
    rowconstraints = [
        ([
            (row, col) for col in cols
            if (row, col) in cells
        ], 1)
        for row in rows
    ]
    colconstraints = [
        ([
            (row, col) for row in rows
            if (row, col) in cells
        ], 1)
        for col in cols
    ]
    plusconstraints = [
        ([
            (row, diag - row) for row in rows
            if diag - row in cols 
        ], numRooks)
        for diag, numRooks in Counter(plusdiags).items()
    ]
    minconstraints = [
        ([
            (row, row - diag) for row in rows
            if row - diag in cols
        ], numRooks)
        for diag, numRooks in Counter(mindiags).items()
    ]
    constraints = rowconstraints + colconstraints + plusconstraints + minconstraints
    # Translate generic format to how python-constraint package works 
    problem = Problem()
    problem.addVariables(cells, [0, 1])
    for cells, numRooks in constraints:
        problem.addConstraint(ExactSumConstraint(numRooks), cells)
    solution = next(problem.getSolutionIter(), None)
    if solution:
        return sorted([cell for cell, hasrook in solution.items() if hasrook] + rooks)

这是一个运行示例：

# Example input (see image below)
rooks = [(1, 2)]                 # row, col coordinates of each known rook
plusdiag = [3, 7, 7, 7, 10, 10]  # diags identified by row+col sum
mindiag = [1]                    # diags identified by row-col sum

solution = solve(rooks, plusdiag, mindiag)
print(solution)

输入代表这个棋盘和约束：

有一个预先放置的车（用 R 表示）。 𝐷 中的对角线是彩色的，它们的频率用数字表示。例如，黄色的需要 3 个车，并用数字 7 来标识，因为它的方格的坐标加起来是 7。

此测试用例的解决方案是这样的：

...上面示例运行的输出是：

[(0, 3), (1, 2), (2, 5), (3, 7), (4, 6), (5, 4), (6, 1), (7, 0)]