每日一练——04回溯法、四皇后问题

一、回溯法是什么？

基本思想：再包含问题的解空间树中，按照深度优点的策略，从根节点出发深度搜索解空间树，如果包含，就从包含，就从该节点出发继续搜索下去：如果该节点不包含问题的解，就说明以该节点为根节点的子树一定不包含问题的解，那就说明以该节点为根节点的子树一定不包含问题的最终解，因此要跳过对以该节点为根的子树的系统搜索逐层向子树的祖先节点回溯。

二、四皇后问题

1.四皇后问题

问题描述：在N*N的棋盘上，如何无冲突的拜访N个皇后棋子。注意：棋子移动的规则是该棋子所在行、列、45度方向的棋盘格子中不能出现其他皇后棋子，求N个皇后棋子的摆放规则。
问题分析：以四皇后为例子，在4 *4 的格子中放置4枚棋子，要求4枚棋子所出现的棋子的行、列、45度方向上不能有其他棋子的出现，下图所所展示的就就是四皇后其中的一种摆放规则。

2.图解

按照规则往下寻找，如果满足条件则继续往下寻找，如果不满足条件，返回上一下，该节点不会继续往下进行。

其中最下面的第三个是满足条件的

代码如下（示例）：

3.代码展示

#include <stdio.h>
int count = 0;//有多少种解

int is_correct(int i, int j, int (*Q)[4])
{
	int n,m = 0;
	//判断行，行不变，从第0 个元素开始找 如果有两个皇后，则返回0
	for(m=0,n=i;m<4;++m)
	{
		if(Q[n][m] == 1 && m !=j) 
		{
			return 0;
		}
	}
	//判断列
	for(m=j,n=0;n<4;++n)
	{
		if(Q[n][m] == 1 && n !=i) 
		{
			return 0;
		}
	}
	//判断左上角
	for(n=i-1,m=j-1;m>=0 && n>=0;n--,m--)
	{
		if(Q[n][m] ==  1)
		{
			return 0;
		}
	}
	//判断左下角
	for(n=i+1,m=j-1;m>=0 && n<4;n++,m--)
	{
		if(Q[n][m] ==  1)
		{
			return 0;
		}
	}
	//判断右上角
	for(n=i-1,m=j+1;m<4 && n>=0;n--,m++)
	{
		if(Q[n][m] ==  1)
		{
			return 0;
		}
	}
	//判断右下角
	for(n=i+1,m=j+1;m<4 && n<4;n++,m++)
	{
		if(Q[n][m] ==  1)
		{
			return 0;
		}
	}
	//所有条件满足则代表可以沿着该数继续往下搜索
	return 1;
}
void Queen(int j, int (*Q)[4])
{
	int i = 0;
	int k = 0;
	//最后满足条件之后输出
	if(j == 4)
	{
		for(i = 0;i < 4;i++)
		{
			for(j=0;j< 4;j++)
			{
				printf("%d ",Q[i][j]);
			}
			printf("\n");
		}
		printf("\n");
		count++;
		return ;
	}
	for(i = 0;i < 4;++i )
	{
		if(is_correct(i,j,Q))
		{
			//满足条件，置为1
			Q[i][j] = 1;
			//遍历列
			Queen(j+1,Q);
			//该节点不满足条件，将该节点置为0
			Q[i][j] = 0;
		}
	
	}
}
int main(int argc, const char *argv[])
{
	//定义一个4*4的二维数组
	int Q[4][4];
	int i,j=0;
	//初始化
	for(i=0;i<4;i++)
	{
		for(j=0;j<4;j++)
		{
			Q[i][j]=0;
		}
	}
	Queen(0,Q);
	printf("The number of the answers if FOUR_QUEEN are %d \n",count);
	return 0;
}

4.结果

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。