N-queen Chess 使用 python 进行最终水平验证

Question

我正在尝试解决 n 皇后验证问题，其中用户首先为我们打印一个 n 乘 n 矩阵，从 0 到 63 为 8 乘 8。用户键入皇后的位置，然后我们的模型评估它们是否是互相攻击。当 queen input = " 59 24 41 19 52 13 30 47 " 显然 41 和 47 在同一行看到 Q 时，我无法通过第二个测试用例。当同一行的两个皇后互相攻击时，程序应该自动产生“失败”。以下是我的代码和所需的输出：

# Get the size of the board from the user.
n = int(input("n: "))

# Print the board with numbers.
s =''
for i in range(n):
    for j in range(n):
        z = i * n + j
        
        if j != 0:
            s += ' '
        
        if z < 10:
            s += ' '
        s += str(z)
    
    if i != j:
        s += '\n'
print(s)
# Get the queens from the user.
queens = list(map(int, input("Queens: ").split()))

# Print the board with queens.

s =''
for i in range(n):
    for j in range(n):
        z = i * n + j
        
        if j != 0:
            s += ' '
        
        if z < 10:
            if z in queens:
                z = " Q"
            else:
                s += ' '
        elif z > 10:
            if z in queens:
                z = " Q"
            else:
                s +=""
        s += str(z)
    
    if i != j:
        s += '\n'
print(s)
# Check if the queens are in the same row or diagonal.
for i in range(n):
    for j in range(i+1, n):
        try:
            if queens[i] == queens[j]:
                print("FAIL")
                exit()
            if abs(queens[i] - queens[j]) == abs(i-j):
                print("FAIL")
                exit()
        except IndexError:
            pass

# If the queens are not in the same row or diagonal, print success.
print("--> SUCCESS <--")

我需要编辑什么才能产生正确的输出？代码重构表示赞赏

Answer 1

abs(queens[i] - queens[j]) == abs(i-j)

不是正确的支票。皇后列表中的index并不重要。如果您要打乱输入列表，结果应该不会受到影响。然而，对于

abs(i-j)

，这种比较对输入列表中两个皇后位置的距离有多远具有重要意义。

要验证两个皇后是否在同一行，您应该首先从给定位置提取行。为此，您可以使用除以 8:

queens[i] // 8 == queens[j] // 8

如果这个比较成立，那么两个皇后在同一行。可以做类似的事情来检查两个皇后是否共享同一列：

queens[i] % 8 == queens[j] % 8

对于对角线检查，您应该比较位置的行和列的总和（对于一种类型的对角线）或位置的行和列的差异。

因此首先从所有位置提取行和列，然后从那里继续。

您还可以计算 distinct 位置行的数量，并检查是否有 𝑛 不同的行被占用。列和对角线相同。要获得 distinct 值，您可以创建一个

set

（它只能存储唯一值，忽略重复值）。如果该集合的值少于𝑛，您就知道存在重复项。

你还应该检查每个位置是0到𝑛²之间的整数（排除）。

这是一个函数中的所有内容：

def verify(n, queens):
    if any(queen not in range(n*n) for queen in queens):
        return False  # invalid queen position
    rows = [queen // n for queen in queens]
    cols = [queen % n  for queen in queens]
    if len(set(rows)) != n:
        return False  # multiple queens on same row
    if len(set(cols)) != n:
        return False  # multiple queens on same column
    if len(set((i + j for i, j in zip(rows, cols)))) != n:
        return False  # multiple queens on same backward diagonal (\\)
    if len(set((i - j for i, j in zip(rows, cols)))) != n:
        return False  # multiple queens on same forward diagonal (/)"
    return True

您可以按如下方式使用它：

def boardstr(n, queens):
    return "\n".join(
        "".join(("Q" if z in queens else str(z)).rjust(3) for z in range(i, i + n))
        for i in range(0, n*n, n)
    )

def verify(n, queens):
    if len(queens) != n:
        return False  # number of queens is wrong
    if any(queen not in range(n*n) for queen in queens):
        return False  # invalid queen position
    rows = [queen // n for queen in queens]
    cols = [queen % n  for queen in queens]
    if len(set(rows)) != n:
        return False  # multiple queens on same row
    if len(set(cols)) != n:
        return False  # multiple queens on same column
    if len(set((i + j for i, j in zip(rows, cols)))) != n:
        return False  # multiple queens on same backward diagonal (\\)
    if len(set((i - j for i, j in zip(rows, cols)))) != n:
        return False  # multiple queens on same forward diagonal (/)"
    return True

n = int(input("n: "))
print(boardstr(n, []))
queens = list(map(int, input("Queens: ").split()))
print(boardstr(n, queens))
valid = verify(n, queens)
print("--> SUCCESS <--" if valid else "--> FAIL <--")