提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

八皇后问题轻松解决

2023-03-14 22:50:58 时间

八皇后问题：

  • 要在8*8的国际象棋棋盘中放8个皇后，使任意两个皇后都不能互相吃掉。规则是皇后能吃掉同一行、同一列、同一对角线的棋子。如下图：

问题分析：

  • 假设有皇后Q1(x1,y1)和Q2(x2,y2)
  • 不在同一行：x1!=x2
  • 不在同一列：y1!=y2
  • 不在同一左对角线上：x1+ y1 != x2 +y2
  • 不在同一右对角线上：x1-y1 !=x2-y2

问题编程化：

  • 我们用一个一维数组a来表示每个皇后的位置，a[2]=4表示皇后的位置位于a(2,4),即二行四列上
  • 某一行的皇后a[n]不能和之前行的皇后a[i]位置有冲突，那么约束条件为：

1.不在同一列：a[n]!=a[i] 2.不在同一行：因为现在是每一行求一个皇后的位置，所以同一行不会有冲突，不需要考虑。 3.不在同一对左角线：a[n]-a[i] != n-i 4.不在同一右对角线：a[n]-a[i] != -(n-i) 注意：约束条件三和四可以合并为abs(a[n]-a[i]) != abs(n-i)

判断位置合法性的函数：

//判断第n个皇后与之前i个皇后位置是否冲突
bool judge(int a[],int n)
{
	for (int i = 0; i < n; i++)
	{
		if (a[n] != a[i] && abs(a[n] - a[i]) == abs(n - i))
			return true;
	}
	return false;
}

回溯代码思路：

  • 1.回溯出口：当放置的皇后数量为八时(如果是n皇后问题，那么这里为n),打印八皇后放置的位置图
  • 2.回溯主体：找出当前皇后的合适放置位置
  • 3.回溯返回：如果找不到合适放置位置，或者已经放置满了，进行回溯操作，尝试寻找其他放置可能性
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
//记录解的总数
int num;
//判断第n个皇后与之前i个皇后位置是否冲突
bool judge(vector<int>& ret,int n)//这里的n是当前要放置在第n行的皇后，即当前层是n*n的矩阵
{
	//第n行要放置的皇后需要和前面n-1行已经放置的皇后进行检查，看是否产生位置冲突
	for (int i = 0; i <=n-1; i++)
	{
		if (ret[n] == ret[i] || abs(ret[n] - ret[i]) == abs(n - i))
			return false;
	}
	return true;
}
//打印八皇后放置图
void print(vector<int>& ret)
{
	for (int i = 0; i < ret.size(); i++)
	{
		for (int j = 0; j < ret.size(); j++)
		{
			//ret[i]==j，表明i行j列放置了一个皇后，皇后的标志为1
			if (ret[i] == j)
				cout << 1 << " ";
			else
				cout << 0 << " ";
		}
		cout << endl;
	}
	cout << "----------------------------" << endl;
}
//寻找合适位置的函数
void FindPos(int start,int n)//从第几行开始放置皇后，n个皇后需要放置
{
	static vector<int> ret;//记录皇后放置的位置
	//结束条件
	if ((start+1)>n)//start表示当前在从第几行开始放置皇后，如果开始从第n+1行放置皇后，那么表明上一层就找到了一个解
	{
		num++;
		print(ret);
		return;
	}
	else
	{
			//对每一列进行试探，看是否为合适放置皇后的位置
			for (int j = 0; j < n; j++)
			{
				ret.push_back(j);
				//如果当前i行j列能够放置皇后，那么就继续寻找下一个皇后的合适放置位置
				if (judge(ret, start))
				{
					FindPos(start + 1,n);//下一个皇后应该放置在当前行的下一行
				}
				//如果找到了一种解，或者当前状态无解，那么恢复到上一层的状态，去寻找其他可能解
				ret.pop_back();
			}
	}
}
int main()
{
	FindPos(0, 8);
	cout << "解的总数为：" << num << endl;
	system("pause");
	return 0;
}

相关文章