题目内容

n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数n，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数n。

输出格式

每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。

其中”.”表示某一个位置的方格状态为空，”Q”表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围

1≤n≤9

输入样例

4

输出样例

.Q..
…Q
Q…
..Q.

..Q.
Q…
…Q
.Q..

题解

第一种思路：全排列+剪枝。
这是一道基于上题的思路（全排列）+剪枝的问题。因为n皇后要求每一个皇后都拥有独立的行和列，因此为全部的皇后进行全排列的过程中，一定存在不满足要求的部分，这些部分需要通过剪枝操作将其剔除出结果，最后剩下的即为答案。

第二种思路：枚举全部格子进行搜索。
每个格子都进行枚举，每个格子都有两种选择，放皇后和不放皇后，然后继续往下寻找，直到皇后全部放好之后输出即可。这里同样需要注意递归后的保护现场。

代码

// //第一种方法思路代码
// #include <iostream>

// using namespace std;

// const int N = 20;

// int n;
// char g[N][N];
// bool col[N],dg[N],udg[N]; //设col为列数组，dg为对角线数组，udg为反对角线数组。同时因为枚举的时候按行枚举，因此保证了每行只有一个，所以不用加row[N]这个数组。

// void dfs(int u){
//     if (u == n){//找到一组方案 
//         for (int i = 0; i < n; i++) puts(g[i]);
//         puts("");
//         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] = '.';
//         }
//     }
// }

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

//第二种方法思路代码
#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){ // x y 定位棋盘的格子位置，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;
    }
    //不放皇后
    dfs(x,y+1,s);
    
    //放皇后
    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] = '.';
    }
    
}

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;
}