C語言如何使用回溯法解八皇后問題

這篇文章給大家分享的是有關(guān)C語言如何使用回溯法解八皇后問題的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過來看看吧。

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

一、問題描述

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

二、源代碼

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

void put_queen(int x, int y, vector<vector<int>>&attack)
{//實(shí)現(xiàn)在(x,y)放置皇后，對(duì)attack數(shù)組更新，xy表示放置皇后的坐標(biāo)，attack表示是否可以放置皇后
	//方向數(shù)組，方便后面對(duì)8個(gè)方向進(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個(gè)距離延伸
	{
		for (int j = 0; j < 8; j++)//遍歷8個(gè)方向
		{
			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存儲(chǔ)皇后的位置
//attack標(biāo)記皇后的攻擊范圍
//solve存儲(chǔ)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存儲(chǔ)至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存儲(chǔ)具體的擺放位置，<vector<string>>存放一種解法，二維vector存放全部解法
	vector<vector<string>>solve;//存儲(chǔ)最后結(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;
}

三、測(cè)試結(jié)果

四皇后

八皇后

感謝各位的閱讀！關(guān)于“C語言如何使用回溯法解八皇后問題”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！