写在开头：实验结果截图8皇后太多截不完，用4皇后代替了，只需将n->8就行

图解算法过程：

下面分析中的$(x,y)$相当于上面的$(u,i)$
反对角线 $y=x+b$, 截距 $b=y-x$，因为我们要把 $b$ 当做数组下标来用，显然 $b$ 不能是负的，所以我们加上 n （实际上$+n+4$,$+2n$都行），来保证是结果是正的，即 $y-x+n$
而对角线 $y=-x+b$ 截距是 $b=y+x$，这里截距一定是正的，所以不需要加偏移量
核心目的：找一些合法的下标来表示dg或udg是否被标记过，所以如果你愿意，你取 udg[n−u+i] 也可以，只要所有(u,i)对可以映射过去就行

算法一：DFS 按行枚举，时间复杂度O（n!）

const int N=25;
int n;
char g[N][N];
bool dg[N],udg[N],col[N];//对角线 dg[u+i]，反对角线udg[n−u+i]中的下标 u+i和 n−u+i 表示的是截距
int k=1;
void dfs(int u)
{if(u==n){cout<<n<<"皇后的第"<<k++<<"种方案："<<endl;for(int i=0;i<n;i++)cout<<g[i]<<endl;cout<<endl;return; }for(int i=0;i<n;i++){if(!col[i]&&!dg[u+i]&&!udg[n-u+i]){g[u][i]='Q';col[i]=dg[u+i]=udg[n-u+i]=true;//标记 dfs(u+1);col[i]=dg[u+i]=udg[n-u+i]=false;//还原现场g[u][i]='.'; }}
}
void solve()
{cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]='.';dfs(0);
}

运行结果截图：

算法二：DFS按每个元素枚举 时间复杂度$O(2^{n^2})$，每个位置都有两种情况，总共有 $n^2$ 个位置

const int N=25;
int n;
char g[N][N];
bool dg[N],udg[N],col[N],row[N];
int k=1;
void dfs(int x,int y,int s)
{if(y==n)y=0,x++;if(x==n){if(s==n){cout<<n<<"皇后的第"<<k++<<"种方案："<<endl;for(int i=0;i<n;i++)cout<<g[i]<<endl;cout<<endl;}return;}if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n])//选 {g[x][y]='Q';row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;dfs(x,y+1,s+1);row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;g[x][y]='.';}//不选dfs(x,y+1,s); 
}
void solve()
{cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]='.';dfs(0,0,0);
}

运行结果截图

算法三：二进制对空间进行优化

int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
const int N=25;
int n;
vector<string>g;
vector<vector<string>>res;
int cnt=1;
void dfs(int a,int b,int c,int k)
{if(k==n){res.push_back(g);return;}for(int i=~(a|b|c)&((1<<n)-1);i;i-=lowbit(i)){int p=lowbit(i);g[k][log2(p)]='Q';//计算第几位是1，用对数函数log2十分方便dfs((a|p)<<1,(b|p)>>1,c|p,k+1);g[k][log2(p)]='.';}
}
void solve()
{cin>>n;vector<string>board(n,string(n,'.'));g=board;dfs(0,0,0,0);for(int i=0;i<res.size();i++){cout<<n<<"皇后的第"<<cnt++<<"种方案："<<endl;for(int j=0;j<res[i].size();j++){cout<<res[i][j]<<endl;}cout<<endl;}
}

运行结果截图