N皇后问题-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

N皇后问题

简介:

八皇后问题是一个古老而著名的问题,它是回溯算法的典型例题。该问题是十九世纪德国著名数学家高斯于1850年提出的:在8行8列的国际象棋棋盘上摆放着 八个皇后。若两个皇后位于同一行、同一列或同一对角线上,则称为它们为互相攻击。
现在要求使这八个皇后不能相互攻击,即任意两个皇后都不能处于同一行、同一列或同一对角线上,问有多少种摆法。

解题思路

在递归方式中,pos[i]表示第i行的皇后摆在第pos[i]列上。也可以使用循环来模拟递归过程。

实现代码

打印所有摆放方式:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Queens {
public:
    int nQueens(int n) {
        vector<int> pos(n, 0);
        int i = 0;
        fun(n, pos, i);
        return 0;
    }

    void fun(int n, vector<int>& pos, int i)
    {
        if (i == n)
        {
            return;
        }
        for (int k = 0; k < n; k++)
        {
            pos[i] = k;
            if (check(pos, i))
            {
                if (i == n - 1)
                {
                    show(pos);
                }
                else
                {
                    fun(n, pos, i + 1);
                }
            }
        }
    }

    bool check(vector<int> pos, int i)
    {
        for (int k = 0; k < i; k++)
        {
            if (pos[k] == pos[i] || abs(k - i) == abs(pos[k] - pos[i]))
            {
                return false;
            }
        }
        return true;
    }

    void show(vector<int> pos)
    {
        for (int i = 0; i < pos.size(); i++)
        {
            for (int j = 0; j < pos.size(); j++)
            {
                if (pos[i] == j)
                {
                    cout<<'+'<<" ";
                }
                else
                {
                    cout<<'0'<<" ";
                }
            }
            cout<<endl;
        }
        cout<<endl;
    }
};

int main()
{
    Queens q;
    q.nQueens(8);
}

打印摆放种类:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Queens {
public:
    int nQueens(int n) {
        vector<int> pos(n, 0);
//        递归方式
//        int count = 0;
//        fun(n, pos, 0, count);
//        return count;

//        非递归方式
        return fun2(n, pos);
    }

    //非递归方式
    int fun2(int n, vector<int> pos)
    {
        int i = 0;
        pos[i] = -1;
        int count = 0;
        while (i >= 0)
        {
            pos[i]++;
            while (pos[i] < n && !check(pos, i))
            {
                pos[i]++;
            }
            if (pos[i] < n)
            {
                if (i == n - 1)
                {
                    count++;
                }
                else
                {
                    i++;
                    pos[i] = -1;
                }
            }
            else
            {
                i--;
            }
        }

        return count;
    }

    //递归方式
    void fun(int n, vector<int>& pos, int i, int& count)
    {
        if (i == n)
        {
            return;
        }
        for (int k = 0; k < n; k++)
        {
            pos[i] = k;
            if (check(pos, i))
            {
                if (i == n - 1)
                {
                    count++;
                }
                else
                {
                    fun(n, pos, i + 1, count);
                }
            }
        }
    }

    bool check(vector<int> pos, int i)
    {
        for (int k = 0; k < i; k++)
        {
            if (pos[k] == pos[i] || abs(k - i) == abs(pos[k] - pos[i]))
            {
                return false;
            }
        }
        return true;
    }
};

int main()
{
    Queens q;
    for (int i = 1; i <= 12; i++)
    cout<<q.nQueens(i)<<endl;
}


转载:http://blog.csdn.net/foreverling/article/details/47380027

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章