经典问题之八皇后问题

﹏ヽ暗。殇╰゛Y 2022-05-19 04:06 223阅读 0赞

# 问题描述： #

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后，为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

# 思路： #

我们先来考虑，某个位置是否能够放皇后，如下图

![70][]

两个皇后的位置是<1,1>，<2,3>，那么接下来的第三个皇后该怎么放呢？

1、设row为行，col为列，我们可以从第3行第0列开始循环。

2、当col与前面已放置皇后的列相等时，我们不放。

3、当abs（row - i） = abs（col - j），表示右上斜线与左上斜线已有皇后，我们不放，i,j表示已放置皇后的行值和列值。

然后采用递归方式，递归第row+1行，摆放下一个皇后，当row = 8时，表示8个皇后全部放置完成，即为一种可行的8皇后摆放方法。

# 代码实现： #

#include <iostream>
    #include <cmath>
    
    using namespace std;
    int count = 0;  //统计摆放方法数
    
    void queen(int row,int a[])
    {
        int flag; //用于标记该位置是否能够摆放皇后
        if(row == 8){
            count++;  //递归到第八行，表示8个皇后全部放置完成，摆放方法+1
            return;
        }
        else{
            //从第0列开始，逐列判断，是否能够摆放皇后
            for(int col = 0; col < 8; col++){
                a[row] = col;  //表示第row第col列
                flag = 1;
                for(int i = 0; i < row; i++){
                        //如果 a[i] 列有值，则不能放值
                                    //如果行值差等于列值差的绝对值相等，表示左上斜线或右上斜线有值
                    if(a[i] == col || abs(i - row) == abs(a[i] - col)){   //判断皇后位置是否符合条件
                        flag = 0;
                        break;//不符合则退出 换另一列
                    }
                }
                if(flag)
                    queen(row+1,a);//符合则递归下一行
            }
        }
    }
    int main()
    {
        int a[8]; //存放皇后的位置，以数组下标为行，值为列
        queen(0,a); //从第0行开始递归
        cout << "总共有 " <<count << " 种摆法" << endl;
        return 0;
    }

# 运行结果： #

![70 1][]

[70]: /images/20220519/8866de929ff743c6906f6436ca17a307.png
[70 1]: /images/20220519/1b8c0a961f46453080efcc2867920e03.png