《n皇后问题(回溯法)原创》由会员分享,可在线阅读,更多相关《n皇后问题(回溯法)原创(2页珍藏版)》请在金锄头文库上搜索。
n后问题问题描述在nxn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nxn格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。算法分析解向量:(x1,x2,xn) 显约束:xi=1,2,n 隐约束:1) 不同列:xixj2) 不处于同一正、反对角线:|i-j|xi-xj|代码实现:classQueenfriendintnQueen(int)private:boolPlace(intk);voidBacktrack(intt);intn,/皇后个数*n;/当前解longsum;/当前已找到的可行方案数;boolQueen:Place(intk)for(intj=1;jn)sum+;/达到叶结点elsefor(inti=1;i=n;i+)/搜索子结点xt=i;/进入第i个子结点if(Place(t)Backtrack(t+1);intnQueen(intn)QueenX;/初始化XX.n=n;X.sum=0;int*p=newintn+1;for(inti=0;i=n;i+)pi=0;X.x=p;X.Backtrack(1);/对整个解空间回溯搜索deletep;returnX.sum;运行结果: