函数调用关系观察:深度优先搜索解决八皇后问题

代码:

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

void dfs(int x, const int size, int* a, int* row, int* col, int* ld, int* rd, int& total);
int main()
{
	const int size = 10000;
	int row[size] = { 0 };
	int col[size] = { 0 };
	int ld[2 * size] = { 0 };
	int rd[2 * size] = { 0 };
	int a[size] = { 0 };
	int total = 0;
	dfs(0, size, a, row, col, ld, rd, total);
	cout << "总方案数: " << total;
	return 0;
}

void dfs(int x, const int size, int* a, int* row, int* col, int* ld, int* rd, int & total)
{
	//cout << x;
	if (x == size)
	{
		/*
		cout << "正确解法:";
		for (int i = 0; i < size; i++)
		{
			cout << a[i] << " ";
		}
		cout << endl;
	*/
		total++;
		return;
	}
	cout << "正在测试第 " << x + 1 << " 行的情况\n";
	for (int y = 0; y < size; y++)
	{
		//cout << "正在测试第 " << x + 1 << " 行第 " << y + 1 << " 列的情况:";
		if (!row[x] && !col[y] && !ld[x - y + size] && !rd[x + y])
		{
			//cout << "第 " << x + 1 << " 行第 " << y + 1 << " 列的情况是成功的,此时为:";
			//cout << "成功\n";
			a[x] = y + 1;

			row[x] = 1;//封闭行
			col[y] = 1;//封闭列
			ld[x - y + size] = 1;//封闭左对角线
			rd[x + y] = 1;//封闭右对角线
			/*
			for (int i = 0; i < size; i++)
			{
				cout << a[i] << " ";
			}
			cout << endl;
			*/
			dfs(x + 1, size, a, row, col, ld, rd, total);//进行下一层回溯

			row[x] = 0;//还原行
			col[y] = 0;//还原列
			ld[x - y + size] = 0;//还原左对角线
			rd[x + y] = 0;//还原右对角线
		}
		else
		{
			//cout << "  但是在第 " << x + 1 << " 行第 " << y + 1 << " 列的情况是失败的\n";
			//cout << "失败\n";
		}
	}
}
  1. 观察函数栈的调用:方法一:设置断点,在每个断点处检查变量的值;方法二:设置断点,并且在函数调用时和返回后都进行输出
  2. 程序以八皇后问题为例,这里使用的方法二,运行之后可以看出进行深度优先搜索时函数调用栈满足后进先出的原则,
  3. 将八皇后的棋盘大小设置为10000,在测试第2869~2875行的情况时发生了溢出,每次发生溢出时深度不完全相同

发表评论

电子邮件地址不会被公开。 必填项已用*标注