解法一：(时间复杂度n*n!)

#include<iostream>
using namespace std;

const int N = 20;//数据开20，因为在n*n的矩阵中主副对角线都有2n-1条
int n;
char q[N][N];   //表示棋盘，“.”表示空位，“Q”表示皇后
bool col[N],z[N],f[N];  //col表示当前位置的列、z和f分别表示当前主副对角线是否没有皇后

void dfs(int u)//u为行下标
{
    if(u == n)//如果u与n相等(即u等于最大行下标加一)，说明棋盘放置完毕，已找到一组方案
    {
        for(int i=0; i<n; i++)  puts(q[i]);//输出每一行并返回
        puts("");
        return ;
    }
    for(int i=0; i<n; i++)//用i表示列下标开始遍历每一列
    {   //主副对角线的下标可以联想一元一次方程y=x+b及y=-x+b，用截距来表示分别是b=y-x或x+y
        //但数组下标不能为负，所以将y-x加上偏移量n用y-x+n表示(这里y表示行下标u，x表示列下标i)
        if(!col[i] && !z[i+u] && !f[u-i+n]){//如果当前位置的列及主副对角线都没有皇后
            q[u][i] = 'Q';  //在该位置放置皇后
            col[i] = z[i+u] = f[u-i+n] = true;  //标记该列及主副对角线已存在皇后
            dfs(u+1);   //递归进入下一行
            col[i] = z[i+u] = f[u-i+n] = false; //递归结束开始回溯，应恢复现场
            q[u][i] = '.';  
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            q[i][j] = '.';//初始化棋盘

    dfs(0);//从第一行开始放置，传入下标0

    return 0;
}

解法二：(时间复杂度2^(n^2))

//枚举每一个格子，判断是否放皇后，当枚举到第n*n个格子就完成一种方案，再判断是否符合
#include<iostream>
using namespace std;

const int N = 20;//数据开20，因为在n*n的矩阵中主副对角线都有2n-1条
int n;
char q[N][N];   //表示棋盘，“.”表示空位，“Q”表示皇后
bool row[N],col[N],z[N],f[N];  //row和col表示当前位置的行列、z和f分别表示当前主副对角线是否没有皇后

void dfs(int x,int y,int s)//
{
    if(y==n)    y = 0, x++;//按行枚举，如果列下标越界，将其置为0

    if(x == n)//如果x与n相等(即x等于最大行下标加一)，说明已枚举完所有格子
    {
        if(s == n){//判断皇后个数是否满足(某些方案中皇后个数s可能小于n)
            for(int i=0; i<n; i++)  puts(q[i]);//输出每一行并返回
            puts("");
        }
        return ;
    }
    //枚举当前格子的两种选择
    //不放皇后
    dfs(x,y+1,s);//直接走到下一格
    //放皇后
    if(!row[x] && !col[y] && !z[x+y] && !f[y-x+n]){//行列及主副对角线都不能有皇后
        q[x][y] = 'Q';
        row[x] = col[y] = z[x+y] = f[y-x+n] = true;
        dfs(x,y+1,s+1);
        row[x] = col[y] = z[x+y] = f[y-x+n] = false;
        q[x][y] = '.';
    }
}

int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            q[i][j] = '.';//初始化棋盘

    dfs(0,0,0);//从第一个格子开始枚举，传入其下标。第三个格子表示已放置的皇后个数

    return 0;
}