52. N 皇后 II
52. N皇后Ⅱ
我以前写这题的时候就没搞明白，她是怎么计算两边的对角线的，然后我今天自己推了一下，但是我是横竖进行遍历，传的参数是放了几个皇后，导致不仅时间复杂度很高，而且还可能导致一行里面有多个皇后，还导致搜索空间爆炸，所以应该采用dfs传入行数这一个参数，然后遍历每列的每一个
N 皇后问题有一个隐含但必须遵守的约束：
✅每行只能放一个皇后
void dfs(int x, int y, int t) { for (int i = x; i < w; i++) { for (int j = y; j < w; j++) { // 尝试在 (i,j) 放皇后 } } }会导致：
- 同一行可能放多个皇后
- 比如先在
(0,0)放一个，回溯后又在(0,1)放一个 → 违反规则！
- 比如先在
- 大量重复解
- 皇后顺序不同但位置相同（如先放 (0,0) 再放 (1,1)，或先放 (1,1) 再放 (0,0)）会被算作两个解
- 搜索空间爆炸
- 你是在所有格子中“任意选 k 个不冲突的位置”，而不是“每行选一个”
✅ 正确策略：按行递归，每行只放一个皇后
标准做法是：
- 第
t层 DFS 处理第t行 - 在该行尝试每一列
j - 这样天然保证每行一个皇后，且不会重复计数
题目：
题解：
class Solution { int w; //竖 boolean[] col; //左对角线——x+y boolean[] left; //右对角线——w-1+y-x boolean[] right; int res; //以行数为参数 void dfs(int row) { if(row==w) { res++; return; } for(int j=0;j<w;j++) { if(col[j]==false&&left[row+j]==false&&right[w-1+j-row]==false) { //放皇后 col[j]=true; left[row+j]=true; right[w-1+j-row]=true; dfs(row+1); //恢复现场 col[j]=false; left[row+j]=false; right[w-1+j-row]=false; } } } public int totalNQueens(int n) { w = n; col = new boolean[n]; left = new boolean[2*n]; right = new boolean[2*n]; res = 0; dfs(0); return res; } })
)
