八皇后位运算优化

八皇后(N=8)基本要求:

  1. 任意两点不得在同一列或同一行
  2. 任意两点连线不得与对角线重合或平行

方法

  1. 采用递归方法进行寻找
  2. 利用位运算来进行优化

变量

  1. board(棋盘) 初始化:board=(1>>N)-1 (board二进制表示为 :11111111)
  2. row(存储已经放上棋子的列,表示为1 ,未存放棋子的列表示为0 )
  3. left_Diagonal(自左向右的对角线)(本行不可存放棋子的位置表示为一,可存放的表示为0)
  4. right_Diagonal(自右向左的对角线) (同上)
  5. all是全局变量,表示所有可以使八皇后成立的条件
//给出代码,来帮助理解(最好手动进行位运算来帮助理解)
void check(int row,int left_Diagonal,int right_Diagonal)
{
	int pos,place;//pos中存放本行所有可以存放点的位置,place是选出的其中一个点,从右向左依次选出
	//此处用的int只有八位,若想进行更多位的皇后,可以采用long类型
	if(row!=board)
	{
		pos=board&(~(row|left_Diagonal|right_Diagonal));//row,le,ri,z中存放的是不可以放棋子的点,取并集,就是全部的不可存放点,按位取反,不可存放点变为零,在于board进行按位与运算,得到pos中为1的位置是可存放点)
		while(pos)//当pos不为零时即存在可以放职棋子得位置)
		{
		place=pos&(~pos+1);//可以获得右侧起第一个可放置点的位置。
		pos=pos-p;//使用完之后将已经尝试过的点的位置变为0,防止循环后面重复使用
		check(row|place,(left_Diagonal|place)>>1,(right_Diagoal|place)<<1);
		}
	}
	else
	all++;
}


上一篇:牛客网 meeting 【树的直径】


下一篇:Oracle 实现与mysql中find_in_set函数的兼容