八皇后问题二维数组方法带分析的详细程序

1、问题： 将八个皇后放入 8*8 的方格中，她们不相互攻击（每个皇后都能攻击同行 同列同一条斜线上的棋子）。 分析： 定义一个二维数组 z99 （用行列的 1-8，数组的每个元素的初值为 1）表 示 8*8 的棋盘， 8 个皇后互相不能攻击，则每行只有一个皇后，一位数组 a9 ， ai是第i行所在的列（例如a1=2,表示第1行上的皇后在第2列）。约束条 件： 第 t 个皇后不与前 1-t 个皇后同行同列同斜线。故放下第 t 个皇后要改变棋 盘的布局，从此皇后的位置向下，与她同列同斜线上的元素都标记为0。 1、第一个皇后可以放在第一行的（ 1-8）任意位置，故用 for 循环，保证 第一个皇后可以

2、从第一个位置循环放到第八个位置，将第一行的皇后放好，根 据约束条件改变棋盘布局，即改变 z的值，然后调用本身即A （2） 2、放第二个皇后之前把棋盘的布局（z的所有元素的值）保存到x 中。由于第一个皇后已放好，并影响后面其他的皇后，第二个皇后要根据 z2i 判断哪里能放，若 z2i=1 ，表示可以放下，由于可以放的位置不止一个，故还 要用for循环来控制，放下后根据约束条件改变 z，调用本身A （3） 3、重复步骤2。若第t行全为0即ztN+1中所有元素都是0,返回上一次 调用。将此行（返回后的那行）上的皇后往后移动，在移动之前要将布局更 新，即让z=x叩，移动到满足约束条件，若都不满足则返回

3、上一级调用，重 复步骤3。若t=8,满足放入棋盘的约束条件，则放入，并输出结果，返回上一 级调用,继续查找合适的位置。 #include #define N 8 void A(int t); int zN+1N+1; int w=1;/ 只在结果输出时用到，控制是否输出 “-” int aN+1=0;/ 定义数组 a 并初始全部元素赋值为 0 void main()int i,j; for(i=1;i=N;i+) for(j=1;j=N;j+) zij=1;/ 对二维数组初始化 printf( 八皇后问题的解： n);A(1);/ 从第 1个皇后开始 void A(int t)int i,y,

4、t1,t2,d1,d2; int xN+1N+1;/ 用来存放 t 皇后放入棋盘之前，棋盘的状态 if(t=1)for(d1=1;d1=N;d1+) for(d2=1;d2=N;d2+) Xd1d2=zd1d2;让二维数组x等于t皇后放入前棋盘状态 zfor(i=1;i=N;i+) for(d1=1;d1=N;d1+) for(d2=1;d2=N;d2+) Zd1d2=xd1d2;将未放t时的初始状态给z,每次返回时或/调度进入 时执行 at=i; t1=i;t2=i; for(y=t+1;y=N;y+)/ 改变棋盘布局 zyi=0;/t 所在列 if(t11) zy-t2=0;/ 向左下延伸

5、的的斜线 A(t+1); else if(t=N)for(d1=1;d1=N;d1+) for(d2=1;d2=N;d2+) Xd1d2=zd1d2;让二维数组x等于t皇后放入前棋盘/状态z for(i=1;i=N;i+)for(d1=1;d1=N;d1+) for(d2=1;d2=N;d2+) Zd1d2=xd1d2;将未放t时的初始状态给z,每次/返回时或调度进入 时执行 if(zti)/ 判断 zti 是否能够放下 tat=i; t1=i; t2=i; if(t=N)如果最后一个也放入了则输出结果printf(第%d种解： n,w+); for(d1=1;d1,d1,d1,ad1); printf(n); else/zti 为 0if(i=N)/t 行的所有元素为 0 return; continue; 继续 for 循环f