1.N 皇后问题是什么？

N 皇后问题就是在一个 N×N 格的国际象棋上摆放 N 个皇后，使其不能互相攻击。也就是任意两个皇后不能放在同一行、同一列或者同一斜线上。

例如下面是一个 8×8 格的棋盘，假设有一个皇后摆放在位置 y=0, x=3 的地方，那么红色位置都是不可以摆放东西的。

2.代码

代码是由 ACer Sˇsuper 提供的，我主要是解释一下代码的关键部分，代码如下:

3.代码解读

3.1 res 返回什么

res 是保存所有正确解的列表，例如上面的代码运行会得到 [ [1, 3, 0, 2], [2, 0, 3, 1] ]，说明会有两个正确的解。每一个解也是一个列表，表示每一行皇后的 x 位置，例如 [1, 3, 0, 2] 表示第一行皇后 x=1，第二行皇后 x=3，第三行皇后 x=0，第四行皇后 x=2。这两个解可以用下面的图表示。

3.2 Lie、Pie 和 Na 分别有什么用

先说结论:

Lie: 一个用于保存对应的解的列表，就是 res 里面的解，表示每一行皇后的 x 位置。

Pie: 用于标记当前位置 (x,y) 对应的右下斜线 (这一斜线上面不能再放皇后, 后面会解释)。

Na: 用于标记当前位置 (x,y) 对应的左下斜线 (这一斜线上面不能再放皇后, 后面会解释)。

回到刚刚的那幅图，假设皇后放到 y=0, x=3 的地方。在这种情况下，接下来的行有三种格子是不能放的。

首先是 x=3 的格子不能放了，如下图。因为 Lie 保存了 x 的信息，因此对于接下来的 y，直接判断 x not in Lie 就行。如果 x 相同就肯定不能放。

其次是右下斜线上的格子不能放了，如下图。那么就需要一个独一无二的数字来标识这一条斜线，这些斜线是有规律的。例如下面的红色斜线包含的点有 (y=1,x=4)、(y=2,x=5)、(y=3,x=6)、(y=4,x=7)，存在一个规律 y-x=-3，是个固定的值。因此可以用 y-x 来作为右下斜线的标识，并保存到 Pie 列表里。对于新的行，直接判断 y-x not in Pie 就行，和 Lie 类似。

最后是左下斜线上的格子不能放了，如下图。同样是有规律的，例如下面的红色斜线包含的点有 (y=1,x=2)、(y=2,x=1)、(y=3,x=0)，存在一个规律 y+x=3，是个固定的值。因此可以用 y+x 来作为左下斜线的标识，并保存到 Na 列表里。对于新的行，直接判断 y+x not in Na 就行。

4.结尾

哈哈，代码的逻辑比较难用语言描述，只能尽量说的通俗易懂一些，有哪里不对的，欢迎大家讨论指正。

N 皇后问题代码解读