P1219 [USACO1.5] 八皇后 Checker Challenge——题解

解题思路

按行放置皇后。用三个布尔数组分别记录已占用的列、主对角线编号 row-col+n、副对角线编号 row+col。每行按列号从小到大尝试，因此完整方案按字典序产生。计数所有方案，只在最初三个方案完成时输出。

复杂度分析

搜索复杂度取决于剪枝后的状态数，粗略上界为 $O(n!)$；辅助空间 $O(n)$。

易错点

两类对角线必须分别标记；输出只限前三个方案，但总数仍要继续搜索到结束。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int n,pos[15]; bool col[15],d1[30],d2[30]; long long cnt=0;
void dfs(int r){
    if(r>n){
        cnt++;
        if(cnt<=3){for(int i=1;i<=n;i++){if(i>1)cout<<' ';cout<<pos[i];}cout<<'\n';}
        return;
    }
    for(int c=1;c<=n;c++) if(!col[c]&&!d1[r-c+n]&&!d2[r+c]){
        pos[r]=c;col[c]=d1[r-c+n]=d2[r+c]=true;
        dfs(r+1);
        col[c]=d1[r-c+n]=d2[r+c]=false;
    }
}
int main(){cin>>n;dfs(1);cout<<cnt<<'\n';return 0;}

#include <bits/stdc++.h> using namespace std; int n,pos[15]; bool col[15],d1[30],d2[30]; long long cnt=0; void dfs(int r){ if(r>n){ cnt++; if(cnt<=3){for(int i=1;i<=n;i++){if(i>1)cout<<' ';cout<<pos[i];}cout<<'\n';} return; } for(int c=1;c<=n;c++) if(!col[c]&&!d1[r-c+n]&&!d2[r+c]){ pos[r]=c;col[c]=d1[r-c+n]=d2[r+c]=true; dfs(r+1); col[c]=d1[r-c+n]=d2[r+c]=false; } } int main(){cin>>n;dfs(1);cout<<cnt<<'\n';return 0;}