(原创精品)n后问题(回溯法)

《(原创精品)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;j

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;}