C语言如何使用回溯法解八皇后问题

这篇文章给大家分享的是有关C语言如何使用回溯法解八皇后问题的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

八皇后问题（N皇后问题）的回溯法求解

一、问题描述

在一个国际象棋棋盘上放置八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法，并推广到N皇后情况。

二、源代码

#include#include#includeusing namespace std;void put_queen(int x, int y, vector>&attack){//实现在(x,y)放置皇后，对attack数组更新，xy表示放置皇后的坐标，attack表示是否可以放置皇后        //方向数组，方便后面对8个方向进行标记        static const int dx[] = { -1,-1,-1,0,0,1,1,1 };        static const int dy[] = { -1,0,1,-1,1,-1,0,1 };        attack[x][y] = 1;//将皇后位置标记为1        //通过两层for循环，将该皇后可能攻击到的位置标记        for (int i = 1; i < attack.size(); i++)//从皇后位置向1到n-1个距离延伸        {                for (int j = 0; j < 8; j++)//遍历8个方向                {                        int nx = x + i * dx[j];//生成的新位置行                        int ny = y + i * dy[j];//生成的新位置列                        //在棋盘范围内                        if (nx >= 0 && nx < attack.size() && ny >= 0 && ny < attack.size())                                attack[nx][ny] = 1;//标记为1                }        }}//回溯算法//k表示当前处理的行//n表示n皇后问题//queen存储皇后的位置//attack标记皇后的攻击范围//solve存储N皇后的全部解法void backtrack(int k, int n, vector& queen,        vector>& attack,        vector>& solve){        if (k == n)//找到一组解        {                solve.push_back(queen);//将结果queen存储至solve                return;        }        //遍历0至n-1列，在循环中，回溯试探皇后可放置的位置        for (int i = 0; i < n; i++)        {                if (attack[k][i] == 0)//判断当前k行第i列是否可以放置皇后                {                        vector> tmp = attack;//备份attack数组                        queen[k][i] = 'Q';//标记该位置为Q                        put_queen(k, i, attack);//更新attack数组                        backtrack(k + 1, n, queen, attack, solve);//递归试探k+1行的皇后的位置                        attack = tmp;//恢复attack数组                        queen[k][i] = '.';//恢复queen数组                }        }}vector>solveNQueens(int n){//string存储具体的摆放位置，>存放一种解法，二维vector存放全部解法        vector>solve;//存储最后结果        vector>attack;//标记皇后的攻击位        vectorqueen;//保存皇后位置        //使用循环初始化attack和queen数组        for (int i = 0; i < n; i++)        {                attack.push_back((vector()));                for (int j = 0; j < n; j++)                {                        attack[i].push_back(0);                }                queen.push_back("");                queen[i].append(n, '.');        }        backtrack(0, n, queen, attack, solve);        return solve;//返回结果数组}int main(){        //int num;        //cin >> num;//输入皇后数        初始化attack数组        //vector> attack(num,vector(num, 0));        初始化queen数组        //string s;        //for (int i = 0; i < num; i++)s += '.';        //vector queen(num, s);        int n;        cin >> n;        vector>result;        result = solveNQueens(n);        cout << n << "皇后共有" << result.size() << "种解法" << endl;        for (int i = 0; i < result.size(); i++)        {                cout << "解法" << i + 1 << ":" << endl;                for (int j = 0; j < result[i].size(); j++)                {                        cout << result[i][j] << endl;                }                cout << endl;        }        system("pause");        return 0;}

三、测试结果

四皇后

八皇后

感谢各位的阅读！关于"C语言如何使用回溯法解八皇后问题"这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！