bigywater.tech
算法与数据结构 · LeetCode 51

LeetCode 51. N 皇后

把 n 个皇后放到 n × n 的棋盘上，使任意两个皇后都不在同一行、同一列、同一条对角线上，返回所有不同的摆法（每种摆法用 n 个字符串表示棋盘，Q 是皇后，. 是空位）。做法是回溯：一行放一个皇后，逐行往下放，每放一个之前检查它所在的列和两条对角线有没有被占。判断对角线有一个巧妙的编码：同一条"主对角线"（\ 方向）上的格子 r - c 相同，同一条"副对角线"（/ 方向）上的格子 r + c 相同。本文用真实数据展示漏掉一条对角线会多出多少"解"，实测回溯与枚举全部排列的耗时，给出五种语言的实现，并把每一步的放置和冲突做成分步演示。

50
组随机对拍，与暴力解的结果全部一致
78 步
分步演示，每一帧都来自解法的真实执行，另附 5 种语言实现

题意与示例

完整题目见官方页面（链接在文末）。摆法的先后顺序不作要求，按集合比较。基准解枚举 0 到 n-1 的全部排列（每行一个皇后，排列决定了皇后所在的列，这样行和列自动不冲突），只检查对角线，是与回溯完全不同的写法。一共 8 组用例，n 从 1 到 8：

真实实测 · 本机执行输出
输入 [1]
输出 [["Q"]]
输入 [2]
输出 []
输入 [3]
输出 []
输入 [4]
输出 [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
输入 [5]
输出 [["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]
输入 [6]
输出 [[".Q....","...Q..",".....Q","Q.....","..Q...","....Q."],["..Q...",".....Q",".Q....","....Q.","Q.....","...Q.."],["...Q..","Q.....","....Q.",".Q....",".....Q","..Q..."],["....Q.","..Q...","Q.....",".....Q","...Q..",".Q...."]]

解的个数，以及漏掉一条对角线的后果

下面是 n 从 1 到 9 时本文解法得到的解的个数，以及一个漏掉副对角线（只检查列和主对角线）的写法得到的个数：

真实实测 · 本机执行输出
n | 解的个数（solve）| 漏掉副对角线的写法得到的个数
1 |             1 |          1
2 |             0 |          1
3 |             0 |          3
4 |             2 |          7
5 |            10 |         23
6 |             4 |         83
7 |            40 |        405
8 |            92 |       2113
9 |           352 |      12657

正确的个数依次是 1、0、0、2、10、4、40、92、352（n = 2 和 n = 3 没有解），与文献里已知的 N 皇后解的个数一致（n = 8 是 92，这是这个问题最有名的一个数）。漏掉一条对角线的写法给出的数远大于正确值：n = 8 时是 2113 而不是 92，n = 2 时甚至认为有 1 个解，而实际上一个都没有。这类错误在小棋盘上会碰巧对（n = 1），棋盘大一点就暴露了。

回溯加冲突集合：五种语言的实现

用三个集合（或布尔数组）记录被占用的列、主对角线（r - c，Java、Go、JavaScript、C++ 里加上 n - 1 使下标非负）、副对角线（r + c）。dfs(r) 尝试在第 r 行的每一列放皇后：三处都没被占才放；放完递归到下一行；返回时撤销。放满 n 行就把 queens（每行皇后所在的列）翻译成 n 个字符串收集起来。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。

Python · 解法代码def solve(n): res = [] cols, diag1, diag2 = set(), set(), set() # 已经被占用的列、主对角线（r-c 相同）、副对角线（r+c 相同） queens = [] # queens[r] = 第 r 行皇后所在的列 def dfs(r): if r == n: res.append(["." * c + "Q" + "." * (n - c - 1) for c in queens]) return for c in range(n): if c in cols or r - c in diag1 or r + c in diag2: continue # 同列或同对角线：会互相攻击 cols.add(c) diag1.add(r - c) diag2.add(r + c) queens.append(c) dfs(r + 1) queens.pop() # 回溯：撤销这一行的皇后 cols.remove(c) diag1.remove(r - c) diag2.remove(r + c) dfs(0) return res
真实实测 · Python · 前几组用例的输出
$ python3 solution.py   # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON
[1]  →  [["Q"]]
[2]  →  []
[3]  →  []
[4]  →  [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
[5]  →  [["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]
[6]  →  [[".Q....","...Q..",".....Q","Q.....","..Q...","....Q."],["..Q...",".....Q",".Q....","....Q.","Q.....","...Q.."],["...Q..","Q.....","....Q.",".Q....",".....Q","..Q..."],["....Q.","..Q...","Q.....",".....Q","...Q..",".Q...."]]
Java · 解法代码class Solution { private int n; private boolean[] cols, diag1, diag2; // 已占用的列、主对角线（r-c+n-1）、副对角线（r+c） private int[] queens; // queens[r] = 第 r 行皇后所在的列 private List<List<String>> res; public List<List<String>> solveNQueens(int n) { this.n = n; cols = new boolean[n]; diag1 = new boolean[2 * n]; diag2 = new boolean[2 * n]; queens = new int[n]; res = new ArrayList<>(); dfs(0); return res; } private void dfs(int r) { if (r == n) { List<String> board = new ArrayList<>(); for (int c : queens) { char[] row = new char[n]; Arrays.fill(row, '.'); row[c] = 'Q'; board.add(new String(row)); } res.add(board); return; } for (int c = 0; c < n; c++) { if (cols[c] || diag1[r - c + n - 1] || diag2[r + c]) continue; // 同列或同对角线：会互相攻击 cols[c] = diag1[r - c + n - 1] = diag2[r + c] = true; queens[r] = c; dfs(r + 1); cols[c] = diag1[r - c + n - 1] = diag2[r + c] = false; // 回溯：撤销这一行的皇后 } } }
真实实测 · Java · 前几组用例的输出
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl
[1]  →  [["Q"]]
[2]  →  []
[3]  →  []
[4]  →  [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
[5]  →  [["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]
[6]  →  [[".Q....","...Q..",".....Q","Q.....","..Q...","....Q."],["..Q...",".....Q",".Q....","....Q.","Q.....","...Q.."],["...Q..","Q.....","....Q.",".Q....",".....Q","..Q..."],["....Q.","..Q...","Q.....",".....Q","...Q..",".Q...."]]
Go · 解法代码func solveNQueens(n int) [][]string { res := [][]string{} cols := make([]bool, n) diag1 := make([]bool, 2*n) // 主对角线：r-c+n-1 相同 diag2 := make([]bool, 2*n) // 副对角线：r+c 相同 queens := make([]int, n) // queens[r] = 第 r 行皇后所在的列 var dfs func(r int) dfs = func(r int) { if r == n { board := make([]string, n) for i, c := range queens { board[i] = strings.Repeat(".", c) + "Q" + strings.Repeat(".", n-c-1) } res = append(res, board) return } for c := 0; c < n; c++ { if cols[c] || diag1[r-c+n-1] || diag2[r+c] { // 同列或同对角线：会互相攻击 continue } cols[c], diag1[r-c+n-1], diag2[r+c] = true, true, true queens[r] = c dfs(r + 1) cols[c], diag1[r-c+n-1], diag2[r+c] = false, false, false // 回溯：撤销这一行的皇后 } } dfs(0) return res }
真实实测 · Go · 前几组用例的输出
$ go build -o bin . && ./bin < cases.jsonl
[1]  →  [["Q"]]
[2]  →  []
[3]  →  []
[4]  →  [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
[5]  →  [["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]
[6]  →  [[".Q....","...Q..",".....Q","Q.....","..Q...","....Q."],["..Q...",".....Q",".Q....","....Q.","Q.....","...Q.."],["...Q..","Q.....","....Q.",".Q....",".....Q","..Q..."],["....Q.","..Q...","Q.....",".....Q","...Q..",".Q...."]]
JavaScript · 解法代码function solveNQueens(n) { const res = []; const cols = new Array(n).fill(false); const diag1 = new Array(2 * n).fill(false); // 主对角线：r-c+n-1 相同 const diag2 = new Array(2 * n).fill(false); // 副对角线：r+c 相同 const queens = new Array(n).fill(0); // queens[r] = 第 r 行皇后所在的列 const dfs = (r) => { if (r === n) { res.push(queens.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1))); return; } for (let c = 0; c < n; c++) { if (cols[c] || diag1[r - c + n - 1] || diag2[r + c]) continue; // 同列或同对角线：会互相攻击 cols[c] = diag1[r - c + n - 1] = diag2[r + c] = true; queens[r] = c; dfs(r + 1); cols[c] = diag1[r - c + n - 1] = diag2[r + c] = false; // 回溯：撤销这一行的皇后 } }; dfs(0); return res; }
真实实测 · JavaScript · 前几组用例的输出
$ node run.js < cases.jsonl
[1]  →  [["Q"]]
[2]  →  []
[3]  →  []
[4]  →  [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
[5]  →  [["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]
[6]  →  [[".Q....","...Q..",".....Q","Q.....","..Q...","....Q."],["..Q...",".....Q",".Q....","....Q.","Q.....","...Q.."],["...Q..","Q.....","....Q.",".Q....",".....Q","..Q..."],["....Q.","..Q...","Q.....",".....Q","...Q..",".Q...."]]
C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { int n; vector<bool> cols, diag1, diag2; // 已占用的列、主对角线（r-c+n-1）、副对角线（r+c） vector<int> queens; // queens[r] = 第 r 行皇后所在的列 vector<vector<string>> res; void dfs(int r) { if (r == n) { vector<string> board; for (int c : queens) { string row(n, '.'); row[c] = 'Q'; board.push_back(row); } res.push_back(board); return; } for (int c = 0; c < n; c++) { if (cols[c] || diag1[r - c + n - 1] || diag2[r + c]) continue; // 同列或同对角线：会互相攻击 cols[c] = diag1[r - c + n - 1] = diag2[r + c] = true; queens[r] = c; dfs(r + 1); cols[c] = diag1[r - c + n - 1] = diag2[r + c] = false; // 回溯：撤销这一行的皇后 } } public: vector<vector<string>> solveNQueens(int n) { this->n = n; cols.assign(n, false); diag1.assign(2 * n, false); diag2.assign(2 * n, false); queens.assign(n, 0); dfs(0); return res; } };
真实实测 · C++ · 前几组用例的输出
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl
[1]  →  [["Q"]]
[2]  →  []
[3]  →  []
[4]  →  [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
[5]  →  [["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]
[6]  →  [[".Q....","...Q..",".....Q","Q.....","..Q...","....Q."],["..Q...",".....Q",".Q....","....Q.","Q.....","...Q.."],["...Q..","Q.....","....Q.",".Q....",".....Q","..Q..."],["....Q.","..Q...","Q.....",".....Q","...Q..",".Q...."]]
真实实测 · 本机执行输出
共 8 组用例（含边界），以暴力解的结果为基准逐组比对：
  Python      通过 8/8
  Java        通过 8/8
  Go          通过 8/8
  JavaScript  通过 8/8
  C++         通过 8/8

耗时实测：回溯对枚举排列

n 分别为 4、6、8、9，每个规模取三次中最快的一次，基准解是枚举全部 n! 个排列后检查对角线：

真实实测 · 本机执行输出
n | 暴力解 | 本文解法
         4 |     0.010 ms | 0.008 ms
         6 |     0.232 ms | 0.092 ms
         8 |    14.410 ms | 1.522 ms
         9 |      （未测，太慢） | 6.493 ms

n = 8 时，回溯 1.52ms，枚举排列 14.41ms，约 9.5 倍（枚举要检查 40320 个排列，回溯提前剪掉了大部分）。回溯从 n = 8 到 n = 9 增长约 4.3 倍，n 更大时会继续快速增长，所以这道题的 n 只到 9。基准在 n = 9 时没有再测。

随机对拍

Python 版本另外对 n 从 1 到 7 的随机取值和枚举排列做了对拍：

真实实测 · 本机执行输出
随机对拍 50 组（n 取 1 到 7 的随机值），solve 与 brute 的结果全部一致。

n 只有 1 到 8 这几个值，固定用例已经覆盖了全部小规模输入。另外四种语言只在上面 8 组固定用例上验证过，其中包含了每个 n 的完整解集。

分步演示：n = 4

下面的演示用 n = 4，共 2 个解。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的解集与 solve 的返回值一致。琥珀色是已经放下的皇后，蓝色是正在尝试的位置。注意"同列""同主对角线""同副对角线"三种冲突各自的提示，以及最后几行"回到上一行换一个位置"的回溯帧。

N 皇后：n = 4
已放置的皇后正在尝试的位置

    参考与说明

    • 官方题目页：LeetCode 51. N 皇后。本文只用自己的话概括了题意，完整约束以官方页面为准。
    • 数据来自本机真实运行，五种语言的版本写在页脚；耗时对比只用 Python 测量。
    • 没有覆盖：利用棋盘对称性只搜索一半再翻倍的优化；位运算的版本（见下一题）。
    京ICP备2026067502号-1京公网安备11010502063487号