用C++实现8皇后问题+代码

首先感谢B站小姐姐耐心讲解

主要思路：

  • 用二维列表表示摆放皇后后的攻击位置，（即1表示不可放，0表示可放），记为attack。如图

    4ca9e01a1e3644c68223a746494c95dd.png

    c81557333c7140d1917473a95f161897.png

  • 每行放置一个皇后后，更新attack，然后遍历下一行的每列，通过判断该位置是否为0，寻找可放位置（注意要备份attack，以回溯）
  • 关于棋盘用一维queen来表示，用“.”表示空，“Q”表示皇后

49e22789385a45f784ec5c5df7d2c580.png

  •  最后将每种棋盘摆放方法记录

 代码：

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

vector<vector<string>> solveNQueens(int n);
void backtrack(int k, int n, vector<string>& queen, vector<vector<int>>& attack, vector<vector<string>>& solve);//k表示下一个需要摆放皇后行位置
void put_queen(int x, int y, vector<vector<int>>& attack);

int main() {
	vector<vector<string>> res;  //保存棋盘摆放情况
	res = solveNQueens(8);
	cout << "8皇后问题一共有"<<res.size()<<"种情况"<<endl;
	//展示
	cout << "结果如下：" << endl;
	for (int i = 0; i < res.size(); i++) {
		cout << "第" << i+1 << "种" << endl;
		for (int j = 0; j < res[i].size(); j++) {
			cout << res[i][j] << endl;
		}
	}
	return 0;
}
vector<vector<string>> solveNQueens(int n) {
	vector<vector<string>> solve; //保存最终结果
	vector<vector<int>> attack;  //保存皇后攻击位置  0表示不攻击；1表示攻击
	vector<string>queen;  //保存皇后位置
	//1.初始化
	for (int i = 0; i < n; i++) {
		attack.push_back(vector<int>());
		for (int j = 0; j < n; j++) {
			attack[i].push_back(0);
		}
		queen.push_back("");
		queen[i].append(n, '.');//结尾添加n个.
	}
	//求
	backtrack(0, n, queen, attack, solve);
	return solve;
}

void backtrack(int k, int n, vector<string>& queen, vector<vector<int>>& attack, vector<vector<string>>& solve)
{
	if (k == n) {
		//找到一组解
		solve.push_back(queen);
		return;
	}
	//
	for (int i = 0; i < n; i++) {  //遍历第k行的每一列，找到可以放皇后的位置
		if (attack[k][i] == 0) {  //找到
			vector<vector<int>> temp = attack;//备份，便于回溯
			queen[k][i] = 'Q'; //皇后位置标记为Q
			put_queen(k, i, attack);//放皇后后，更新attack
			backtrack(k + 1, n, queen, attack, solve);//递归，试探第k+1行能不能放皇后
			attack = temp;//回溯，回复attack，查找其他可能
			queen[k][i] = '.';//取消皇后放置位置
		}
	}
}

void put_queen(int x, int y, vector<vector<int>>& attack)
{
	//放置皇后后，更新attack
	static const int dx[] = { -1,-1,-1,0,1,1,1,0 };
	static const int dy[] = { -1,0,1,1,1,0,-1,-1 };
	attack[x][y] = -1;
	for (int i = 1; i < attack.size(); i++) {
		for (int j=0;j<8;j++)
		{
			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;
			}
		}
	}
}

 运行结果部分截图：

95677b11aeea4651bba65522a77d23c2.png