n后问题回溯法.docxVIP

实验四 n后问题实验目的 1.?????? 了解皇后相互攻击的条件：如果任意两个皇后在同一行，同一列或同一对角线，则她们相互攻击。2.?????? 运用迭代的方法实现n皇后问题，求解得到皇后不相互攻击的一个解二．实验内容? 基本思路：用n元组x[1:n]表示n后问题的解，其中x[i]表示第i个皇后放在棋盘的第i行的第x[i]列。抽象约束条件得到能放置一个皇后的约束条件：(1)x[i]!=x[k]; (2)abs(x[i]-x[k])!=abs(i-k)。应用回溯法，当可以放置皇后时就继续到下一行，不行的话就返回到第一行，重新检验要放的列数，如此反复，直到将所有解解出。在回溯法中，递归函数Backtrack(1)实现对整个解空间的回溯有哪些信誉好的足球投注网站。Backtrack(i)有哪些信誉好的足球投注网站解空间的第i层子树。类Queen的数据成员记录解空间的节点信息，以减少传给Backtrack函数的参数。sum记录当前已找到的可行方案数。运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于有哪些信誉好的足球投注网站的解空间结构；（3）以深度优先的方式有哪些信誉好的足球投注网站解空间，并且在有哪些信誉好的足球投注网站过程中用剪枝函数避免无效有哪些信誉好的足球投注网站。三．实验结果四.源代码：#includeiostream#includestdlib.husing namespace std;class Queen{friend int nQueen(int);private:bool Place(int k);void Backtract(int t);int n,*x;long sum; //可行方案数};bool Queen::Place(int k){for(int j=1;jk;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;return true;}void Queen::Backtract(int t){if (tn) {sum++;cout第sum种方法：;for(int i=1;i=n;i++)coutx[i] ;coutendl;}else{for(int i=1;i=n;i++){x[t]=i;if(Place(t)) Backtract(t+1);}}}int nQueen(int n){Queen X;X.n=n;X.sum=0;int *p=new int[n+1];for(int i=0;i=n;i++)p[i]=0;X.x=p;X.Backtract(1);delete []p;return X.sum;}void main(){int n,m;cout请输入皇后个数:;cinn;m=nQueen(n);coutendl;cout有m种可行方法endl;system(pause);}