八皇后(N=8)基本要求:
- 任意两点不得在同一列或同一行
- 任意两点连线不得与对角线重合或平行
方法
- 采用递归方法进行寻找
- 利用位运算来进行优化
变量
- board(棋盘) 初始化:board=(1>>N)-1 (board二进制表示为 :11111111)
- row(存储已经放上棋子的列,表示为1 ,未存放棋子的列表示为0 )
- left_Diagonal(自左向右的对角线)(本行不可存放棋子的位置表示为一,可存放的表示为0)
- right_Diagonal(自右向左的对角线) (同上)
- 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++;
}