n皇后(1<=n<=10)问题的通用行数,9行解决。
//
/*
n皇后问题
1<=n<=10
Count=QUEENNUM*QUEENNUM-1;
Num=QUEENNUM;
Attack=0;
*/
#define QUEENNUM 2
int NQueen( int Count,int Num,__int64 Attack )
{
__int64 ONE=1;
if( (Num==0) || ( Count==-1) ) return (Num==0)?1:0;
__int64 CulAttack= (ONE<<(Count/QUEENNUM) ) | ((ONE<<((Count%QUEENNUM))+QUEENNUM)) | (ONE<<(QUEENNUM*2+(QUEENNUM+Count%QUEENNUM-Count/QUEENNUM))) | (ONE<<(QUEENNUM*4+(Count/QUEENNUM+Count%QUEENNUM)));
if( ((CulAttack&Attack)!=0) ) return NQueen(Count-1,Num,Attack);
return NQueen(Count-1,Num,Attack)+NQueen(Count-1,Num-1,Attack|CulAttack);
}
//
如果仅需解决8皇后问题,那就更简单了
int EightQueen()
{
return 92;
}
//
程序说明
-- 如果纠结于皇后之间不能互相攻击,10行内是搞不定的,必须转换问题
对n皇后问题
定义1: 建立(n+2)*(n+2)的棋盘,其中最外围成为壁,共有4*(n+1)个节点,称为壁节点
定义2: 每个皇后定义4种攻击方式:-- | \ / (横线,竖线,左斜线,右斜线)。
定理1: 每个皇后对壁节点攻击8次,每一种攻击各两次。
推论:
情况1: 任意两个皇后之间不能相互攻击
情况2: 任意一个壁节点最多承受4次方式不同攻击
当棋盘中存在n个皇后时,情况1 为 情况2 的充分必要条件。
结论:
仅需要判断每个壁节点的攻击方式不重复即可。
优化:
由于每个皇后攻击的壁节点对称,因此每种攻击仅需一半的攻击节点。
-- n
| n
\ 2*n
/ 2*n
程序思想:
1. 将n*n的棋盘编号,0 -- n*n-1
2. 判断,当皇后处于位置i时,其4种攻击方式所攻击的壁节点编号
3. 若某壁节点已经被攻击,则皇后不得处于该位置
4. 若无壁节点被重复攻击,则皇后可能处于该位置
5. 采用bit位标注,最大为64bit,因此该函数最多能够解决到10皇后问题
//
感谢:
1. 题主的问题,若不存在这一限制,不会这么想,还是挺有意思的。
2. 的代码提供了灵感。