八皇后问题详解

冷不防 2022-05-29 12:57 138阅读 0赞

**目录**

*  问题描述：
 *  问题分析：
 *  代码思路：

# **问题描述：** #

要在8\*8的国际象棋棋盘中放8个皇后，使任意两个皇后都不能互相吃掉。规则是皇后能吃掉同一行、同一列、同一对角线的棋子。如下图即是两种方案：  
![这里写图片描述][20180324111723256]  
![这里写图片描述][20180324111734415]

问有多少种摆法。高斯认为有76种方案。

1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

计算机发明后，有多种方法可以解决此问题。

# **问题分析：** #

算法思路：  
首先我们分析一下问题的解，我们每取出一个皇后，放入一行，共有八种不同的放法，然后再放第二个皇后，同样如果不考虑规则，还是有八种放法。于是我们可以用一个八叉树来描述这个过程。从根节点开始，树每增加一层，便是多放一个皇后，直到第8层（根节点为0层），最后得到一个完全八叉树。紧接着我们开始用深度优先遍历这个八叉树，在遍历的过程中，进行相应的条件的判断。以便去掉不合规则的子树。  
根据上述描述，我们可以得到如果两个皇后Q1(x1, y1)和Q2(x2, y2)不符合要求，则以下四个条件之一必符合。  
1 ) x1== x2(表示两个皇后刚好在同一行)

2 ) y1=y2(表示两个皇后不能再同一列)

3 ) x1+ y1 == x2 +y2 （斜向正方向）

4 ) x1 - y1 == x2 - y2（斜向反方向）

我们将这种思想转换为程序思想来进行实现的话，可以使用一个数组a来记录每个皇后的位置，比如a\[2\]=4,就意味着该皇后的位置是在(2,4)上。  
某一行的皇后a\[n\]不能和之前的皇后a\[i\]位置有冲突，约束条件为：

a、不在同一列：a\[n\] != a\[i\]

b、不在同一行：因为现在是每一行求一个皇后的位置，所以同一行不会有冲突，不需要考虑。

c、不在同一对左角线：a\[n\]-a\[i\] != n-i。 结合数学知识来看待当前这个问题，可以把它理解为斜率  
举例，a\[1\]=2（1,2）和a\[2\]=3（2,3）是在同一左对角线上的，不满足题意。  
d、不在同一右对角线：a\[n\]-a\[i\] != -(n-i)  
举例，a\[1\]=8和a\[2\]=7这两个点在同一条直线上。  
条件c和d可以合成：abs(a\[n\]-a\[i\]) != abs(n-i)  
然后我们就得到了判断位置合法性的函数

bool judge(int a[],int n){
       //判断函数，检测皇后位置是否合法 
        for(int i=1;i<n;i++){
       //将第n个皇后的位置，依次与之前的皇后进行合法性检查 
            if(a[i]==a[n]||abs(n-i)==abs[a[n]-a[i]])//如果在同一行，同一列，或者是正斜线，反斜线，为假 
                return false;
        }
        return true;
    }

# **代码思路：** #

现在进行模块化的程序设计思想，我们把这道题的代码分为以下几个模块儿

*  判断模块，用来对每一行的皇后的位置加以判断，判定其是否合法
 *  输出模块，对于每一种解法，我们要将这种解法输出。
 *  深度搜索模块儿，通过这一模块儿，我们深入进行搜索每一行的皇后的位置的具体情况，并且对于这种情况，进行分析。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    #include<math.h>
    using namespace std;
    int n,i;//n记录是多少个皇后的问题，i记录的是第几个皇后 
    int a[101];//数组下标表示行号，数组值表示列号 
    int sum;//记录有多少种解法 
    bool judge(int a[],int N) //检测当前位置的皇后是否是合法的 
    {  
        for(int j=1;j<N;j++)  
        {  
            if(abs(a[j]-a[N])==abs(j-N) || a[j]==a[N])//见下面注释 
                return false;  
        }  
        return true;  
    }  
    void print_ans(){
       //打印输出每一种解的方案。 
        for(int j=1;j<=n;j++)
            cout<<"<"<<j<<","<<a[j]<<">"<<" ";
        cout<<endl; 
    } 
    void solve(int i){
       //使用该函数来实现递归检测八皇后合法性
        if(i>n){
       //递归出口，每出现一次，意味着得到了一种解 
            sum++; 
            print_ans();//输出答案； 
            return ;
        } 
        for(int j=1;j<=n;j++){
       //每一行8列都尝试走一遍 
            a[i]=j;
            if(judge(a,i)){
       //判断当前皇后是否满足要求，满足则递归至下一层 
                solve(i+1);
            }            
        }
    }
    int main(){
        cin>>n;
        sum=0; 
        solve(1);//
        cout<<"一共有多少组解："<<sum; 
    }

代码中还是有很多不是很完善的地方，如何进行优雅的剪纸操作是一个较大的难题。

[20180324111723256]: /images/20220529/96384e80d0284a91b684c7dee0721a98.png
[20180324111734415]: /images/20220529/a169021ec7c04b5393d8317fe8fd37ef.png