首页 > itarticle > 从火车进站到八皇后

从火车进站到八皇后

admin 11月 13, 2020 0

最近学习了DFS算法，针对这一知识点练习了两道经典的题目，颇有体会。

从代码实现看，为了实现回溯，两种问题都可以用for里嵌套while实现

for 每个分岔点:
	while (满足条件): // 此时如果不满足，则自然用for切到下一种情况
		向下搜索

八皇后问题示例：

bool (int* answers, int n)
{
	if (n == 8)
	{
		print_answer(answers);
		cnt++;
		return true;
	}
	for (int i = 0; i < 8; ++i)
	{
		answers[n] = i;
		if (is_match(answers, n)) 
		{
			find_position(answers, n + 1);
		}
		else
		{
			answers[n] = 0;
		}
	}
	return false;
}