软考常用算法设计方法(一)(5)

【问题】 n皇后问题
　　问题描述：求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局。
　　 这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线4个方向相互捕捉。如图所示，一个皇后放在棋盘的第4行第3列位置上，则棋盘上凡打“×”的位置上的皇后就能与这个皇后相互捕捉。
　　
　　1 2 3 4 5 6 7 8
　　 × ×
　　× × ×
　　 × × ×
　　× × q × × × × ×
　　 × × ×
　　× × ×
　　 × ×
　　 × ×
　　从图中可以得到以下启示：一个合适的解应是在每列、每行上只有一个皇后，且一条斜线上也只有一个皇后。
　　 求解过程从空配置开始。在第1列至第m列为合理配置的基础上，再配置第m+1列，直至第n列配置也是合理时，就找到了一个解。接着改变第n列配置，希望获得下一个解。另外，在任一列上，可能有n种配置。开始时配置在第1行，以后改变时，顺次选择第2行、第3行、…、直到第n行。当第n行配置也找不到一个合理的配置时，就要回溯，去改变前一列的配置。得到求解皇后问题的算法如下：
　　 { 输入棋盘大小值n；
　　 m=0;
　　 good=1;
　　 do {
　　 if (good)
　　 if (m==n)
　　 { 输出解；
　　 改变之，形成下一个候选解;
　　 }
　　 else 扩展当前候选接至下一列；
　　 else 改变之，形成下一个候选解；
　　 good=检查当前候选解的合理性；
　　 } while (m!=0);
　　 }
　　 在编写程序之前，先确定边式棋盘的数据结构。比较直观的方法是采用一个二维数组，但仔细观察就会发现，这种表示方法给调整候选解及检查其合理性带来困难。更好的方法乃是尽可能直接表示那些常用的信息。对于本题来说，“常用信息”并不是皇后的具体位置，而是“一个皇后是否已经在某行和某条斜线合理地安置好了”。因在某一列上恰好放一个皇后，引入一个一维数组（col[ ]），值col[i]表示在棋盘第i列、col[i]行有一个皇后。例如：col [3]=4，就表示在棋盘的第3列、第4行上有一个皇后。另外，为了使程序在找完了全部解后回溯到最初位置，设定col[0]的初值为0当回溯到第0列时，说明程序已求得全部解，结束程序运行。
　　 为使程序在检查皇后配置的合理性方面简易方便，引入以下三个工作数组：
　　（1） 数组a[ ]，a[k]表示第k行上还没有皇后；
　　（2） 数组b[ ]，b[k]表示第k列右高左低斜线上没有皇后；
　　（3） 数组 c[ ]，c[k]表示第k列左高右低斜线上没有皇后；
　　棋盘中同一右高左低斜线上的方格，他们的行号与列号之和相同；同一左高右低斜线上的方格，他们的行号与列号之差均相同。
　　 初始时，所有行和斜线上均没有皇后，从第1列的第1行配置第一个皇后开始，在第m列col[m]行放置了一个合理的皇后后，准备考察第m+1列时，在数组a[ ]、b[ ]和c[ ]中为第m列，col[m]行的位置设定有皇后标志；当从第m列回溯到第m-1列，并准备调整第m-1列的皇后配置时，清除在数组a[ ]、b[ ]和c[ ]中设置的关于第m-1列，col[m-1]行有皇后的标志。一个皇后在m列，col[m]行方格内配置是合理的，由数组a[ ]、b[ ]和c[ ]对应位置的值都为1来确定。细节见以下程序：
　　【程序】
　　# include
　　# include
　　# define maxn 20
　　int n,m,good;
　　int col[maxn+1],a[maxn+1],b[2*maxn+1],c[2*maxn+1];
　　
　　void main()
　　{ int j;
　　 char awn;
　　 printf(“enter n: “); scanf(“%d”,&n);
　　 for (j=0;j<=n;j++) a[j]=1;
　　 for (j=0;j<=2*n;j++) cb[j]=c[j]=1;
　　 m=1; col[1]=1; good=1; col[0]=0;
　　 do {
　　 if (good)
　　 if (m==n)
　　 { printf(“列\t行”);
　　 for (j=1;j<=n;j++)
　　 printf(“%3d\t%d\n”,j,col[j]);
　　 printf(“enter a character (q/q for exit)!\n”);
　　 scanf(“%c”,&awn);
　　 if (awn==’q’||awn==’q’) exit(0);
　　 while (col[m]==n)
　　 { m--;
　　 a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
　　 }
　　 col[m]++;
　　 }
　　 else
　　 { a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
　　 col[++m]=1;
　　 }
　　 else
　　 { while (col[m]==n)
　　 { m--;
　　 a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
　　 }
　　 col[m]++;
　　 }
　　 good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];
　　 } while (m!=0);
　　}