欢迎来到天天文库
浏览记录
ID:5806100
大小:36.00 KB
页数:2页
时间:2017-12-25
《(原创精品)n后问题(回溯法)》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、n后问题问题描述在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。算法分析•解向量:(x1,x2,…,xn)•显约束:xi=1,2,…,n•隐约束:1)不同列:xi¹xj2)不处于同一正、反对角线:
2、i-j
3、¹
4、xi-xj
5、算法classQueenfriendintnQueen(int)private:boolPlace(intk);voidBa
6、cktrack(intt);intn,//皇后个数*n;//当前解longsum;//当前已找到的可行方案数boolQueen::Place(intk){for(intj=1;j7、8、(x[j]==x[k]))returnfalse;returntrue;}voidQueen::Backtrack(intt){if(t>n)sum++;//达到叶结点elsefor(inti=1;i<=n;i++){//搜索子结点x[t]=i;//进入第9、i个子结点if(Place(t))Backtrack(t+1);}}intnQueen(intn){QueenX;//初始化XX.n=n;X.sum=0;int*p=newint[n+1];for(inti=0;i<=n;i++)p[i]=0;X.x=p;X.Backtrack(1);//对整个解空间回溯搜索delete[]p;returnX.sum;}
7、
8、(x[j]==x[k]))returnfalse;returntrue;}voidQueen::Backtrack(intt){if(t>n)sum++;//达到叶结点elsefor(inti=1;i<=n;i++){//搜索子结点x[t]=i;//进入第
9、i个子结点if(Place(t))Backtrack(t+1);}}intnQueen(intn){QueenX;//初始化XX.n=n;X.sum=0;int*p=newint[n+1];for(inti=0;i<=n;i++)p[i]=0;X.x=p;X.Backtrack(1);//对整个解空间回溯搜索delete[]p;returnX.sum;}
此文档下载收益归作者所有