八皇后问题

蔚落 2022-06-06 00:38 215阅读 0赞

## 枚举法 ##

#include<iostream>
    using namespace std;
    int a[9];
    int check(int n,int a[])         
    {
        int i, j;
        for (int i = 1; i < n; i ++)
        {
            for (int j = i+1; j < n; j++)
            {
                if (a[i] == a[j] || abs(a[i] - a[j]) == abs(i - j)) //不同列，不同对角线（用两个坐标交换相减的绝对值）
                    return 0;
            }
        }
        return 1;
    }
    int main()       //爆搜八皇后
    {
    
        for ( a[1] = 1; a[1] < 9; a[1]++)          //八重嵌套循环
        {
            for ( a[2] = 1; a[2] < 9; a[2]++)
            {
                for ( a[3] = 1; a[3] < 9; a[3]++)
                {
                    for ( a[4] = 1; a[4] < 9; a[4]++)
                    {
                        for ( a[5] = 1; a[5] < 9; a[5]++)
                        {
                            for ( a[6] = 1; a[6] < 9; a[6]++)
                            {
                                for ( a[7] = 1; a[7] < 9; a[7]++)
                                {
                                    for (a[8] = 1; a[8] < 9; a[8]++)
                                    {
    
                                            if (check(9, a) == 0)     //检查函数
                                                continue;
                                            else
                                            {
                                                for (int num = 1; num < 9; num++)
                                                {
                                                    cout << a[num] << " ";
    
                                                }
                                                //goto abc; 可选择设置跳转找到一组数据后退出 
                                            }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
         //abc: return 0; 
        return 0;
    }

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、  
\*\*

## 算法二：加约束枚举 ##

int a[9];
    int check(int k)
    {
        int i;
        for (i = 1; i <= k-1; i++)
        {
            if ((abs(i - k) == abs(a[i] - a[k]))||(a[i] == a[k]))
                return 0;
            //return 1;
        }
        return 1;
    }
    int main()       //加约束条件的爆搜八皇后
    {
    
        for ( a[1] = 1; a[1] < 9; a[1]++)         
        {
            for ( a[2] = 1; a[2] < 9; a[2]++)
            {
                if (check(2, a) == 0)              //每层循环判断是否有冲突，有则跳过不再继续，大大减小时间复杂度
                    continue;
    
                for ( a[3] = 1; a[3] < 9; a[3]++)
                {
                    if (check(3, a) == 0)             
                        continue;
                    for ( a[4] = 1; a[4] < 9; a[4]++)
                    {
                        if (check(4, a) == 0)
                            continue;
                        for ( a[5] = 1; a[5] < 9; a[5]++)
                        {
                            if (check(5, a) == 0)
                                continue;
                            for ( a[6] = 1; a[6] < 9; a[6]++)
                            {
                                if (check(6, a) == 0)
                                    continue;
                                for ( a[7] = 1; a[7] < 9; a[7]++)
                                {
                                    if (check(7, a) == 0)
                                        continue;
                                    for (a[8] = 1; a[8] < 9; a[8]++)
                                    {
    
                                            if (check(9, a) == 0)        //检查函数
                                                continue;
                                            else
                                            {
                                                for (int num = 1; num < 9; num++)
                                                {
                                                    cout << a[num] << " ";
    
                                                }
                                                //goto abc; 可选择设置跳转找到一组数据后退出 
                                            }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
         //abc: return 0; 
        return 0;
    }

——————————————————————————————————————————————————————————————————————————\*\*

## 算法三：非递归回溯法 ##

> # include #
> 
> using namespace std;  
> int a\[20\], n=8; //任意个皇后问题  
> void ouput(int num)  
> \{  
> for(int i = 1; i <= num; i++) //  
> cout << a\[i\] <<” “;  
> \}  
> int check(int k) //检查是否同列，同对角线  
> \{  
> int i;  
> for (i = 1; i <= k-1; i++)  
> \{  
> if ((abs(i - k) == abs(a\[i\] - a\[k\]))||(a\[i\] == a\[k\]))  
> return 0;  
> //return 1;  
> \}  
> return 1;  
> \}  
> void find(int n)  
> \{  
> int k;  
> a\[1\] = 0;  
> k = 1;  
> while (k>0) // 判断是否已经退到最后  
> \{  
> a\[k\] = a\[k\] + 1;  
> while ((a\[k\] <= n) && (check(k) == 0))  
> a\[k\] = a\[k\] + 1;  
> if (a\[k\] <= n) //判断跳出原因是否为知道到放置点  
> \{  
> if (k == n) //再判断是否放满了n个皇后  
> ouput(k+1);  
> else  
> \{  
> k = k + 1;  
> a\[k\] = 0;  
> \}  
> \}  
> else //因为找不到放置点而跳出  
> k = k - 1; //回滚一步  
> \}  
> \}  
> void main()  
> \{  
> //cin >> n;  
> find(n);  
> \}这里写代码片

## 算法四：递归回溯 ##

#include<iostream>
    using namespace std;
    int a[20],b[20],c[40],d[40], n,t,i,j,k;  //任意个皇后问题,t记录解得个数,b记录列，c记录主对角线，d记录次对角线
    void ouput()
    {
        t = t + 1;  
        for(int i = 1; i <= n; i++)
            cout << a[i] <<" ";
    }
    void trya(int i)
    {
        int j;
        for (j = 1; j <= n; j++)
        {
            if ((b[j] == 0) && (c[i + j] == 0) && (d[i - j + n] == 0))   //判断是否冲突
            {
                a[i] = j;                               //第i个皇后的位置
                b[j] = 1;                   //设该列为占领
                c[i + j] = 1;//占领主对角线
                d[i - j + n] = 1;               //占领次对角线
                if (i < n)              
                    trya(i + 1);                //递归进入下一层
                else
                    ouput();
                b[j] = 0;                    //***若该层找不到位置清除占领信息
                c[i + j] = 0;
                d[i - j + n] = 0;
    
            }
        }
    }
    void main()
    {
        cin >> n;
        for (i = 1; i <= n; i = i + 1)
        {
            b[i] = 0;
            c[i] = 0;
            c[n + i] = 0;
            d[i] = 0;
            d[n + i] = 0;
        }
        trya(1);
        cout << "次数为" << t << endl;
    }