N 皇后问题：DFS 搜索空间与剪枝
之前写 N 皇后问题，我用了两种写法。
一种是按行遍历，每一层 DFS 处理一行；另一种是按点遍历，每次从当前位置开始，枚举后面的所有格子。
两种写法都用数组记录列和对角线，check 都是 O(1)，但实际运行起来，性能差距很大。
先看按行遍历的写法：
voiddfs(intu){if(u==n){solutions++;return;}for(intj=0;j<n;j++){if(check(u,j)){col[j]=line[u-j+n]=unline[u+j]=1;dfs(u+1);col[j]=line[u-j+n]=unline[u+j]=0;}}}每一层只处理一行，所以不需要考虑同一行放置多个皇后的情况。
再看按点遍历的写法：
voiddfs(intpos,intcnt){if(cnt==n){solutions++;return;}if(pos==n*n)return;for(intk=pos;k<n*n;k++){intx=k/n,y=k%n;if(check(x,y)){row[x]=col[y]=line[x-y+n]=unline[x+y]=1;dfs(k+1,cnt+1);row[x]=col[y]=line[x-y+n]=unline[x+y]=0;}}}这里有一个问题。
假设第一行还没有放皇后，搜索却已经进入了第二行。那么后续就不可能再回到第一行，因为pos只会递增。
既然每一行必须放置一个皇后，这条搜索路径就已经注定失败了。
但原来的代码并不知道这一点，仍然会继续搜索。
我给两种写法增加了节点数和 check 次数的统计，运行 n = 10。
| 指标 | 按行遍历 | 按点遍历 |
|---|---|---|
| 解的数量 | 724 | 724 |
| DFS 节点 | 35,539 | 7,535,369 |
| check 次数 | 348,150 | 70,450,278 |
| 耗时 | 3.088 ms | 535.993 ms |
按点遍历的 DFS 节点是按行遍历的 212 倍左右。
为了验证这个猜想，我统计了进入 DFS 时，已经越过至少一行空行的节点。
结果是 7,499,830 个，占全部 DFS 节点的约 99.53%。
接下来增加一个剪枝：
voiddfs(intpos,intcnt){nodes++;intnext_row=pos/n;for(intr=0;r<next_row;r++){if(!row[r]){return;}}if(cnt==n){solutions++;return;}if(pos==n*n)return;for(intk=pos;k<n*n;k++){intx=k/n,y=k%n;if(check(x,y)){row[x]=col[y]=line[x-y+n]=unline[x+y]=1;dfs(k+1,cnt+1);row[x]=col[y]=line[x-y+n]=unline[x+y]=0;}}}重新运行：
| 指标 | 剪枝前 | 剪枝后 |
|---|---|---|
| 解的数量 | 724 | 724 |
| DFS 节点 | 7,535,369 | 185,489 |
| check 次数 | 70,450,278 | 1,256,703 |
| 耗时 | 535.993 ms | 14.271 ms |
DFS 节点减少了约 97.54%，耗时减少了约 97.34%。
这就验证了我的猜想：大量性能开销来自那些已经不可能得到完整解，却仍然继续搜索的分支。
不过，剪枝后的按点遍历仍然比按行遍历慢约 4.75 倍。
原因也很简单。剪枝只是提前终止了不可能成功的分支，但按点遍历仍然会枚举其他行的格子，再通过row[]判断这些位置是否合法。
而按行遍历直接规定每一层处理哪一行，从搜索结构上就避免了这些操作。
所以，对于 N 皇后问题，与其在按点遍历的基础上不断增加剪枝，不如直接按行建模。
有时候，优化算法不一定是让每一步执行得更快，而是让不必要的步骤根本不发生。
补充两种搜索空间的结构差异统一节点和检查次数的统计口径
完整代码：
#include<iostream>#include<chrono>usingnamespacestd;namespacev1{constintN=20;intn;intcol[N],line[2*N],unline[2*N];longlongnodes=0;longlongchecks=0;longlongsolutions=0;boolcheck(inti,intj){checks++;return!col[j]&&!line[i-j+n]&&!unline[i+j];}voiddfs(intu){nodes++;if(u==n){solutions++;return;}for(intj=0;j<n;j++){if(check(u,j)){col[j]=line[u-j+n]=unline[u+j]=1;dfs(u+1);col[j]=line[u-j+n]=unline[u+j]=0;}}}voidrun(intnn){n=nn;nodes=checks=solutions=0;for(inti=0;i<N;i++)col[i]=0;for(inti=0;i<2*N;i++)line[i]=unline[i]=0;autot0=chrono::steady_clock::now();dfs(0);autot1=chrono::steady_clock::now();doublems=chrono::duration<double,milli>(t1-t0).count();cout<<"\n[v1 行建模]\n"<<"n = "<<n<<'\n'<<"solutions = "<<solutions<<'\n'<<"nodes = "<<nodes<<'\n'<<"checks = "<<checks<<'\n'<<"time = "<<ms<<" ms\n";}}// namespace v1namespacev3{constintN=20;intn;introw[N],col[N],line[2*N],unline[2*N];longlongnodes=0;longlongchecks=0;longlongsolutions=0;// 进入了多少个包含“前面某行仍为空”的 DFS 状态longlongskipped_nodes=0;// 其中有多少个状态没有成功放满 n 个皇后longlongdead_nodes=0;// 由于越过空行而必然无法得到完整解的状态，按深度统计longlongskipped_by_depth[N+1]={};boolcheck(intx,inty){checks++;return!row[x]&&!col[y]&&!line[x-y+n]&&!unline[x+y];}voiddfs(intpos,intcnt){nodes++;// 检查已经越过的行 [0, pos / n) 是否存在空行intnext_row=pos/n;boolhas_skipped_row=false;for(intr=0;r<next_row&&r<n;r++){if(!row[r]){has_skipped_row=true;break;}}if(has_skipped_row){skipped_nodes++;skipped_by_depth[cnt]++;}if(cnt==n){solutions++;return;}if(pos==n*n){if(has_skipped_row)dead_nodes++;return;}for(intk=pos;k<n*n;k++){intx=k/n;inty=k%n;if(check(x,y)){row[x]=col[y]=line[x-y+n]=unline[x+y]=1;dfs(k+1,cnt+1);row[x]=col[y]=line[x-y+n]=unline[x+y]=0;}}}voiddfs2(intpos,intcnt){nodes++;// 剪枝：已经越过的行必须全部放置过皇后intnext_row=pos/n;for(intr=0;r<next_row;r++){if(!row[r]){return;}}// 已经放满 n 个皇后，找到一个解if(cnt==n){solutions++;return;}// 棋盘已经遍历完，仍未放满 n 个皇后if(pos==n*n){return;}// 从当前位置开始，枚举后续所有格子for(intk=pos;k<n*n;k++){intx=k/n;inty=k%n;if(check(x,y)){// 放置皇后row[x]=col[y]=line[x-y+n]=unline[x+y]=1;dfs2(k+1,cnt+1);// 回溯：撤销皇后row[x]=col[y]=line[x-y+n]=unline[x+y]=0;}}}voidrun(intnn){n=nn;nodes=checks=solutions=0;skipped_nodes=dead_nodes=0;for(inti=0;i<=N;i++)skipped_by_depth[i]=0;for(inti=0;i<N;i++)row[i]=col[i]=0;for(inti=0;i<2*N;i++)line[i]=unline[i]=0;autot0=chrono::steady_clock::now();dfs(0,0);autot1=chrono::steady_clock::now();doublems=chrono::duration<double,milli>(t1-t0).count();cout<<"\n[v3 点级建模]\n"<<"n = "<<n<<'\n'<<"solutions = "<<solutions<<'\n'<<"nodes = "<<nodes<<'\n'<<"checks = "<<checks<<'\n'<<"skipped_nodes = "<<skipped_nodes<<'\n'<<"dead_nodes = "<<dead_nodes<<'\n'<<"time = "<<ms<<" ms\n";cout<<"\n按已放置皇后数量统计 skipped_nodes：\n";for(inti=0;i<=n;i++){cout<<"cnt = "<<i<<": "<<skipped_by_depth[i]<<'\n';}}}// namespace v3intmain(){intn=10;v1::run(n);v3::run(n);return0;}
