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) 来一次检查。使用绝对值函数，这相当于测试 abs(c - col) 是否是两个非负数 (0, row - i).

之一

Answer 2

底部的测试检查每个之前的皇后放置以查看：

如果之前的皇后列布置==当前列布置
如果斜率：abs（当前列 - 前一列）/（当前行 - 前一行）== 1

为了澄清，让我们更改变量名称和测试，包含对每个前一行的两次比较，现在写成：

if all(abs(prev_col - curr_col) not in (0, curr_row - prev_row)
            for prev_row, prev_col in enumerate(col_placement[:row])):

上面是prev_col - curr_col != 0 #queens不在同一列

对于 2.，由于棋盘是正方形，所有对角线斜率都等于 1。可以通过确保 delta y = delta x 来测试 1 的斜率。例如 2/2 = 1，所以 2 == 2.

对于上面重写的测试，测试是：abs(prev_col - curr_col) != curr_row - prev_row。列的 abs() 确保测试两个对角线方向；行不需要 abs()，因为 curr_row 是添加的最后一行。

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

Python N-Queen解法解释

Python N-Queen solution explanation

python-3.x

recursion

backtracking

n-queens