C語言回溯法解八皇后問題(八皇后算法)

更新時間：2021年12月28日 08:47:54 作者：是八阿哥不是bug

這篇文章介紹了C語言回溯法解八皇后問題，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下

八皇后問題（N皇后問題）的回溯法求解

一、問題描述

在一個國際象棋棋盤上放置八個皇后，使得任何兩個皇后之間不相互攻擊，求出所有的布棋方法，并推廣到N皇后情況。

二、參考資料

啥文字都不用看，B站上有個非常詳細(xì)的動畫視頻解說，上鏈接?。?！

Click Here!

三、源代碼

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

void put_queen(int x, int y, vector<vector<int>>&attack)
{//實現(xiàn)在(x,y)放置皇后，對attack數(shù)組更新，xy表示放置皇后的坐標(biāo)，attack表示是否可以放置皇后
	//方向數(shù)組，方便后面對8個方向進(jìn)行標(biāo)記
	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;//將皇后位置標(biāo)記為1
	//通過兩層for循環(huán)，將該皇后可能攻擊到的位置標(biāo)記
	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];//生成的新位置列
			//在棋盤范圍內(nèi)
			if (nx >= 0 && nx < attack.size() && ny >= 0 && ny < attack.size())
				attack[nx][ny] = 1;//標(biāo)記為1
		}
	}
}

//回溯算法
//k表示當(dāng)前處理的行
//n表示n皇后問題
//queen存儲皇后的位置
//attack標(biāo)記皇后的攻擊范圍
//solve存儲N皇后的全部解法
void backtrack(int k, int n, vector<string>& queen,
	vector<vector<int>>& attack,
	vector<vector<string>>& solve)
{
	if (k == n)//找到一組解
	{
		solve.push_back(queen);//將結(jié)果queen存儲至solve
		return;
	}
	//遍歷0至n-1列，在循環(huán)中，回溯試探皇后可放置的位置
	for (int i = 0; i < n; i++)
	{
		if (attack[k][i] == 0)//判斷當(dāng)前k行第i列是否可以放置皇后
		{
			vector<vector<int>> tmp = attack;//備份attack數(shù)組
			queen[k][i] = 'Q';//標(biāo)記該位置為Q
			put_queen(k, i, attack);//更新attack數(shù)組
			backtrack(k + 1, n, queen, attack, solve);//遞歸試探k+1行的皇后的位置
			attack = tmp;//恢復(fù)attack數(shù)組
			queen[k][i] = '.';//恢復(fù)queen數(shù)組
		}
	}
}

vector<vector<string>>solveNQueens(int n)
{//string存儲具體的擺放位置，<vector<string>>存放一種解法，二維vector存放全部解法
	vector<vector<string>>solve;//存儲最后結(jié)果
	vector<vector<int>>attack;//標(biāo)記皇后的攻擊位
	vector<string>queen;//保存皇后位置
	//使用循環(huán)初始化attack和queen數(shù)組
	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, '.');
	}
	backtrack(0, n, queen, attack, solve);
	return solve;//返回結(jié)果數(shù)組
}

int main()
{
	//int num;
	//cin >> num;//輸入皇后數(shù)
	初始化attack數(shù)組
	//vector<vector<int>> attack(num,vector<int>(num, 0));
	初始化queen數(shù)組
	//string s;
	//for (int i = 0; i < num; i++)s += '.';
	//vector<string> queen(num, s);
	int n;
	cin >> n;
	vector<vector<string>>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;
}