python-3.x - Python N-Queen解决方案说明

Question

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

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)，可以立即检查所有这三个数字(0, i - row, row - i).使用绝对值函数，这相当于测试 abs(c - col) 是否是两个非负数 (0, row - i) 之一。