八皇后问题的n种解法.pdf

⼋⼋皇皇后后问问题题的的n种种解解法法

经典的⼋皇后问题：在8×8格的国际象棋上摆放⼋个皇后，使其不能互相攻击，任意两个皇后都不能处于同⼀⾏、同⼀列或同⼀斜线上，

问有多少种摆法。

很早就接触过⼋皇后问题，最近数据结构作业中⼜看到了这个题⽬，仔细研究了⼀波⽹上诸位⼤⽜的博客，发现这个问题居然有这么多有趣

的优化。

1.经典的回溯递归解法：

#includestdio.h

#includeiostream

usingnamespacestd;

//dfs，每⾏只能放⼀个元素，遍历每⾏的每个位置，⽤⼀个⼀维数组记录，最后检查是否符合要求

intans;

intvis[10];

intas(intx){

returnx0?x:-x;

}

oolcheck(intr,intc){

for(inti=1;ir;i++){

if(vis[i]==c)returnfalse;

if(vis[i]-c==r-i||vis[i]-c==i-r)returnfalse;

}

returntrue;

}

voiddfs(intr){

if(r8){

ans++;

return;

}

for(inti=1;i=8;i++){

if(check(r,i)){

vis[r]=i;

dfs(r+1);

vis[r]=0;

}

}

}

main(){

dfs(1);

coutansendl;

}

2.对⾓线检查优化

/*⽤三个数组记录列，左对⾓线，右对⾓线信息，每次判断该位置是否符合要求，只在符合要求位置放置元素。*/

#includeiostream

usingnamespacestd;

constintmaxn=105;

constintmo=100;

typedeflonglongll;

inta[maxn],n=8,ans=0;

ool[maxn],c[maxn],d[maxn];

voidsou(intx){

if(xn){

ans++;

return;

}

for(inti=1;i=n;i++)if(!([i]||c[x+i]||d[x-i+n])){

[i]=c[x+i]=d[x-i+n]=true;

a[x]=i;

sou(x+1);

[i]=c[x+i]=d[x-i+n]=false;

}

}

intmain(){

sou(1);

coutans;

}

3.位运算：

//算法思想与上⼀相同，改⽤三个int来存储信息，采⽤位运算提取合适位置

#includeiostream

#includestdio.h

usingnamespacestd;

intoard;

intn;

intans=0;

voidn_queen(intcol,intld,intrd){

if(col==oard){

ans++;

return;

}

intpos=oard(~(col|ld|rd));

while(pos){

intp=pos(-pos);

pos=pos-p;

n_queen(col|p,(ld|p)1,(rd|p)1);

}

}

intmain(){

cinn;

oard=(1n)-1;

n_queen(0,0,0