Python N-Queen 解决方案说明

Question

我正在从编程面试的元素，递归一章中为 n-queen 问题解决这个非常巧妙的解决方案，但似乎无法理解特定的代码段。如果有人可以解释这里的逻辑，那将非常有帮助。如果检查冲突的条件是我试图在这里解决问题但没有成功。

def n_queens(n: int) -> List[List[int]]:
    def solve_n_queens(row):
        if row == n:
            # All queens are legally placed.
            result.append(col_placement.copy())
            return
        for col in range(n):
            # Test if a newly place queen will conflict any earlier queens place before
            # I am struggling to make sense of this if condition
            if all(abs(c - col) not in (0, row - i)
                for i, c in enumerate(col_placement[:row])):
                    col_placement[row] = col
                    solve_n_queens(row + 1)

    result: List[List[int]] = []
    col_placement = [0] * n
    solve_n_queens(0)
    return result

Answer 1

鉴于棋盘的每一行必须恰好有一个皇后，该解决方案表示为每行皇后的水平位置列表。此外，这个列表是从上到下构建的，因此当插入一个皇后时，它是迄今为止最低的皇后，并且棋盘上的所有其他皇后都必须在其上方的行中。

因此，要检查冲突，只需查看三个方向：在同一列中向上、对角向上和向左以及对角向上和向右。

条件all(abs(c - col) not in (0, row - i))检查这一点，到目前为止，棋盘上的其他皇后。数字分别i, c代表每个皇后的垂直和水平位置；row, col代表当前正在检查冲突的女王的位置。

• 同一列中的冲突意味着c - col == 0。
• 对角线向上和向左的冲突意味着c - col == i - row。
• 对角向上和向右的冲突意味着c - col == row - i。

所有这三个都可以通过取c - col并测试它是否是三个数字之一来立即检查(0, i - row, row - i)。使用绝对值函数，这等效于测试是否abs(c - col)为两个非负数之一(0, row - i)。