n皇后问题算法设计.docVIP

算 法 设 计 及 分 析 n皇后问题---回溯求解 国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动；也可以如同“象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么，在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢？这个问题是伟大数学家高斯在十九世纪中期提出来的，并作了部分解答。高斯在棋盘上放下了N个互不攻击的皇后，他还认为可能有N种不同的放法，这就是有名的“N皇后”问题。如果你动手试试，就一定会发现开头几颗皇后很容易放置，越到后来就越困难。由于我们的记忆有限，很可能在某个位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走弯路，花费大量的精力。因此，必须找到一个简易有效、有条不紊的法则才行。 ）））#includestdio.h int a[20],b[20],c[40],d[40],n,i,k; int t=0; //t记录解的个数 void output() { t=t+1; printf(第%d个解:,t); for(k=1;k=n;k++) printf(%d,a[k]); printf(\n); } void find(int i) { int j; for(j=1;j=n;j++) //第i个皇后有n种可能位置 if(b[j]==0c[i+j]==0d[i-j+n]==0) //判断位置是否冲突 {a[i]=j; //摆放皇后 b[j]=1; //占领第j列 c[i+j]=1;//占领两个对角线 d[i-j+n]=1; if(in) find(i+1); //n个皇后没有摆完，递归摆放下一皇后 else output(); //完成任务，打印结果 b[j]=0; //回溯 c[i+j]=0; d[i-j+n]=0; } } void main() { printf(皇后问题n=); scanf(%d,n); for(i=1;i=n;i++) { b[i]=0;c[i]=0;d[i]=0; c[i+n]=0; d[i+n]=0; } find(1); } n=4时的运行结果： 解的放置方式如图： n=6时的运行结果： 解的放置方式如图： 算法分析： 数组b,c,d分别用来标记冲突。数组代表列冲突，如果某列上已经有皇后，则为1，否则为0数组代表主对角线冲突，如果某条主对角线上已经有皇后，则为1，否则为0数组代表从对角线冲突，如果某条从对角线上已经有皇后，则为1，否则为0。回溯法是一种满足某约束条件的穷举式有哪些信誉好的足球投注网站技术，适应于解决一些组合数相当大的问题。通过问题的分析，深理解，提高理解问题的能力，加强动手能力，增加。