C++ n皇后问题

布满荆棘的人生 2023-10-11 20:21 22阅读 0赞

**目录**

n皇后问题

解析

改进

--------------------

## n皇后问题 ##

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

![d7ff73af1cf2246439cf7cad3f6fd704.png][]

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

**输入格式**

共一行，包含整数 n。

**输出格式**

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

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

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

**注意：行末不能有多余空格。**

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

**数据范围**

1≤n≤9

**输入样例：**

**输出样例：**

.Q..
    ...Q
    Q...
    ..Q.
    
    ..Q.
    Q...
    ...Q
    .Q..

### **解析** ###

对于每一个格子只有放与不放皇后两种选择，那么我们可以枚举每一个格子，那么**时间复杂度**为![O(2^n^2)][O_2_n_2]

**对角线问题，我们怎么判断枚举到的位置所在对角线是否已经有皇后了，借用一位大佬的图，如下：**

![1ad5fa2a07c54517a2009dac94a919d7.png][]

代码如下（附注释）：

#include <iostream>
    using namespace std;
    char s[10][10]; //存放每一种方案
    int n; 
    bool row[10],col[10],dg[20],udg[20]; //b = x + y， 所以对角线和反对角线开两倍
    // u表示已经放上去的皇后个数
    void dfs(int x, int y, int u) {
        if(y == n) y = 0 , x ++; //y到第n列的时候已经超出范围了，因为y的范围是0~n-1
        if(x == n) { // x==n说明已经枚举完n^2个位置了
            if(u == n) { // u==n说明成功放上去了n个皇后
                for(int i = 0 ; i < n; i ++) puts(s[i]);
                puts("");
            }
            return ; //输出方案后回溯
        }
        // 分支1：放皇后
        if(!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
            s[x][y] = 'Q';
            row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
            //恢复现场
            dfs(x, y + 1, u + 1);
            row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
            s[x][y] = '.';
        }
        
        // 分支2：不放皇后
        dfs(x, y + 1, u);
    }
    int main() {
        cin >> n;
        //初始化棋盘
        for(int i = 0 ; i < n ; i ++) 
            for(int j = 0 ; j < n; j ++)
                s[i][j] = '.';
        dfs(0, 0, 0); //一开始放置了0个皇后
        return 0;
    }

### 改进 ###

上面的方式是枚举每一个格子，进一步想一下，棋盘上的每一行和每一列只能有一个皇后，那么我们可不可以直接枚举每一行（或者列）呢？当然是可以的，**时间复杂度**为![O(n \* n!)][O_n _ n]。代码如下（附注释）：

#include <iostream>
    using namespace std;
    char s[10][10]; //存放每一种方案
    int n; 
    bool col[10],dg[20],udg[20]; //b = x + y， 所以对角线和反对角线开两倍
    void dfs(int u) {
        if(u == n) { //n个皇后全部放置
            for(int i = 0 ; i < n ; i ++)  //输出方案
                printf("%s\n",s[i]); 
            puts(""); //题目要求的换行
        }
        for(int i = 0 ; i < n; i ++) {  //对于每一行，我们枚举每一列
            //如果这一列没放过，所在对角线和反对角线也没被放过，那么继续深度搜索
            if(!col[i] && !udg[i + u] && !dg[n - u + i]) {
                col[i] = udg[i + u] = dg[n - u + i] = true;
                s[u][i] = 'Q';
                dfs(u + 1); 
                //恢复现场
                col[i] = udg[i + u] = dg[n - u + i] = false;
                s[u][i] = '.';  
            }
        }
    }
    int main() {
        cin >> n;
        //初始化棋盘
        for(int i = 0 ; i < n ; i ++) 
            for(int j = 0 ; j < n; j ++)
                s[i][j] = '.';
        dfs(0); //一开始放置了0个皇后
        return 0;
    }

[d7ff73af1cf2246439cf7cad3f6fd704.png]: https://img-blog.csdnimg.cn/img_convert/d7ff73af1cf2246439cf7cad3f6fd704.png
[O_2_n_2]: https://latex.csdn.net/eq?O%282%5En%5E2%29
[1ad5fa2a07c54517a2009dac94a919d7.png]: https://img-blog.csdnimg.cn/1ad5fa2a07c54517a2009dac94a919d7.png
[O_n _ n]: https://latex.csdn.net/eq?O%28n%20*%20n%21%29