dfs,

// 1.从1->n按字典序输出

// #include<iostream>
// using namespace std;
// const int N=10010;

// int n;
// int path[N];
// bool st[N];

// void dfs(int x)
// {
//     if(x==n)
//     {
//         for(int i=0;i<n;i++)cout<<path[i]<<' ';
//         puts(" ");
//         return;
//     }
//     for(int i=1;i<=n;i++)
//     if(!st[i])//i还没被标记
//     {
//         path[x]=i;
//         st[i]=true;
//         ///搜索下一位
//         dfs(x+1);

//         //回溯
//         st[i]=false;
//     }
// }
// int main()
// {
//     cin>>n;
//     dfs(0);
//     return 0;
// }

//2.八皇后问题

// #include<iostream>
// using namespace std;
// const int N=10010;
// bool hi[N],hp[N],ph[N];
// char q[N][N];
// int n;

// void dfs(int x)//x代表第几行
// {
//     if(x==n)
//     {
//     for(int i=0;i<n;i++)puts(q[i]);
//     puts(" ");
//     return ;
//     }


//     for(int i=0;i<n;i++)
//     {
//         if(!hi[i]&&!hp[x+i]&&!ph[n-x+i])
//         {
//             hi[i]=hp[x+i]=ph[n-x+i]=true;
//             q[x][i]='Q';
//             dfs(x+1);//递归
//             //回溯
//             hi[i]=hp[x+i]=ph[n-x+i]=false;
//             q[x][i]='.';
//         }

//     }
// }
// int main()
// {
//     cin>>n;
//     for(int i=0;i<n;i++)
//     {
//         for(int j=0;j<n;j++)
//         q[i][j]='.';
//     }
//     dfs(0);
//     return 0;
// }

//3.八皇后问题其他解（非深度优先搜索，而是一个一个找）
#include<iostream>
using namespace std;

const int N=20;
int n;
char g[N][N];
bool row[N],col[N],dg[N],udg[N];

void dfs(int x,int y,int s)
{
    if(y==n)y=0,x++;//找完了下一行
    if(x==n)//找到了最后一行
    {
        if(s==n)//找完了皇后
        {
            for(int i=0;i<n;i++)puts(g[i]);
            puts(" ");
        }
        return;
    }


    //情况1，找到了
    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);//情况2，没找到
}



int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        g[i][j]='.';

    dfs(0,0,0);
    return 0;
}