【例6-51】枚举法求解八皇后问题。
【分析】承上题，仍用诸如{1,5,8,6,3,7,2,4}这样的数列表示八皇后问题的解，不难看出，这恰好是数字1～8的一种全排列。事实上，如果缺某数或某数不止1次地出现，就肯定不是八皇后问题的解。例如{1,5,8,6,3,7,2,5}缺4而5出现两次，相当于棋盘的第4列上什么棋子也没有，第5列上却有两个皇后！注意1～8全排列只是解的必要条件，尚待斜线条件(即沿±45°斜线只有0～1个皇后)作进一步甄别。甄别函数OK()根据斜线条件判断是否八皇后问题的解。在－45°即沿主对角线方向，斜线条件表现为皇后所在行、列号之差的绝对值必须惟一；在＋45°即沿副对角线方向，斜线条件表现为皇后所在行、列号之和必须惟一。程序清单如下
/* ex6-51.c或8queen.c */
#include<stdio.h>
#define N 8 /*皇后数*/
typedef int bool;
main( )
{ int NSOLVE=0; char solve[ ]="???????? ";
int s[N]={1,2,3,4,5,6,7,8},a,b,c,d,e,f,g,h;
int t[N]={1,1,1,1,1,1,1,1}; /*对应元素的忙闲信息,此处规定1:未用; 0:已用*/
for(a=0; a<N; a++)
{ t[a]=0; solve[0]=s[a]+'0';
for(b=0; b<N; b++)if(t[b])
{ t[b]=0; solve[1]=s[b]+'0';
for(c=0; c<N; c++)if(t[c])
{ t[c]=0; solve[2]=s[c]+'0';
for(d=0; d<N; d++)if(t[d])
{ t[d]=0; solve[3]=s[d]+'0';
for(e=0; e<N; e++)if(t[e])
{ t[e]=0; solve[4]=s[e]+'0';
for(f=0; f<N; f++)if(t[f])
{ t[f]=0; solve[5]=s[f]+'0';
for(g=0; g<N; g++)if(t[g])
{ t[g]=0; solve[6]=s[g]+'0';
for(h=0; h<N; h++)if(t[h])
{ t[h]=0; solve[7]=s[h]+'0';
if(OK(solve))
{ printf("%s",solve);
if(++NSOLVE%8==0)printf("\n");
} t[h]=1;
} t[g]=1;
} t[f]=1;
} t[e]=1;
} t[d]=1;
} t[c]=1;
} t[b]=1;
} t[a]=1;
}
printf("\n八皇后问题共有%d个解.\n",NSOLVE);
}
bool OK(char slv[ ])
{ int i,j,sum,dif;
for(i=0; i<N; i++)
{ sum=i+slv[i]; dif=i-slv[i];
for(j=0; j<N; j++)if(j!=i)
{ if(j+slv[j]==sum)return(0);
if(j-slv[j]==dif)return(0);
}
}
return(1);
}
运行结果如下
15863724 16837425 17468253 17582463 24683175 25713864 25741863 26174835
26831475 27368514 27581463 28613574 31758246 35281746 35286471 35714286
35841726 36258174 36271485 36275184 36418572 36428571 36814752 36815724
36824175 37285146 37286415 38471625 41582736 41586372 42586137 42736815
42736851 42751863 42857136 42861357 46152837 46827135 46831752 47185263
47382516 47526138 47531682 48136275 48157263 48531726 51468273 51842736
51863724 52468317 52473861 52617483 52814736 53168247 53172864 53847162
57138642 57142863 57248136 57263148 57263184 57413862 58413627 58417263
61528374 62713584 62714853 63175824 63184275 63185247 63571428 63581427
63724815 63728514 63741825 64158273 64285713 64713528 64718253 68241753
71386425 72418536 72631485 73168524 73825164 74258136 74286135 75316824
82417536 82531746 83162574 84136275
八皇后问题共有92个解.
“横看成岭侧成峰”，八皇后问题的92个解实际上只有12组独立解。图6-2从基本解{1,5,8,6,3,7,2,4}(左上角)出发，沿水平方向相继绘出了(相对于基本解)逆时针旋转90、180、270度情况下得到的衍生解；下方的4幅图则是其正上方图行、列对调后的衍生解。
基本解 逆时针转90° 再逆时针转90° 再逆时针转90°
(15863724) (36428571) (57263148) (82417536)
■□□□□□□□ □□■□□□□□ □□□□■□□□ □□□□□□□■
□□□□■□□□ □□□□□■□□ □□□□□□■□ □■□□□□□□
□□□□□□□■ □□□■□□□□ □■□□□□□□ □□□■□□□□
□□□□□■□□ □■□□□□□□ □□□□□■□□ ■□□□□□□□
□□■□□□□□ □□□□□□□■ □□■□□□□□ □□□□□□■□
□□□□□□■□ □□□□■□□□ ■□□□□□□□ □□□□■□□□
□■□□□□□□ □□□□□□■□ □□□■□□□□ □□■□□□□□
□□□■□□□□ ■□□□□□□□ □□□□□□□■ □□□□□■□□
行列对调 行列对调 行列对调 行列对调
(17582463) (84136275) (63571428) (42736851)
■□□□□□□□ □□□□□□□■ □□□□□■□□ □□□■□□□□
□□□□□□■□ □□□■□□□□ □□■□□□□□ □■□□□□□□
□□□□■□□□ ■□□□□□□□ □□□□■□□□ □□□□□□■□
□□□□□□□■ □□■□□□□□ □□□□□□■□ □□■□□□□□
□■□□□□□□ □□□□□■□□ ■□□□□□□□ □□□□□■□□
□□□■□□□□ □■□□□□□□ □□□■□□□□ □□□□□□□■
□□□□□■□□ □□□□□□■□ □■□□□□□□ □□□□■□□□
□□■□□□□□ □□□□■□□□ □□□□□□□■ ■□□□□□□□
图6-2 基本解{1,5,8,6,3,7,2,4}及其衍生解
【例6-52】用枚举法找出八皇后问题的独立解。
【分析】如何实现行列对调和逆时针转90度是编程的关键。基本解{1,5,8,6,3,7,2,4}中的'1'代表第1行第1列即(1,1)处有皇后、'5'代表(2,5)处有皇后、……'4'代表(8,4)处有皇后；行列对调后变成(1,1)处、(5,2)处、……(4,8)处有皇后。因此下面的程序段
int i,s[8]={1,5,8,6,3,7,2,4},t[8]/*存放行列对调后的衍生解*/;
for(i=1; i<=8; i++)t[s[i-1]-1]=i;
可实现行列对调。观察逆时针转90度后棋盘(相对于基本解)的变化发现，原先位于(i,j)的皇后经旋转到达了(9-j,i)处，如原先的第4行第6列变成了第3行第4列。因此程序段
int i,s[8]={1,5,8,6,3,7,2,4},t[8]/*存放逆时针转90度的衍生解*/;
for(i=1; i<=8; i++)t[8-s[i-1]]=i;
可实现逆时针转90度。程序清单如下(沿用ex6-51.c的主函数)
/* ex6-52.fun */
#include<string.h>
bool OK(char slv[ ])
{ int i,j,sum,dif;
static char sos[100][N+2]; static num=0;
for(i=0; i<N; i++)
{ sum=i+slv[i]; dif=i-slv[i];
for(j=0; j<N; j++)if(j!=i)
{ if(j+slv[j]==sum)return(0);
if(j-slv[j]==dif||j-slv[j]==-dif)return(0);
}
}
if(num)/*如果sos数组已存有衍生解*/
for(i=0; i<num; i++)if(strcmp(slv,sos[i])==0)return(0);
rot(sos[num],slv); rot(sos[num+1],sos[num]); rot(sos[num+2],sos[num+1]);
zhuan(sos[num+3],slv); zhuan(sos[num+4],sos[num]);
zhuan(sos[num+5],sos[num+1]); zhuan(sos[num+6],sos[num+2]);
num+=7; return(1);
}
rot(char d[ ],char s[ ])
{ int i;
for(i=1; i<=N; i++)d[N-(s[i-1]-'0')]=i+'0'; d[N]=' ';
}
zhuan(char d[ ],char s[ ])
{ int i;
for(i=1; i<=N; i++)d[s[i-1]-'0'-1]=i+'0'; d[N]=' ';
}
运行结果如下
15863724 16837425 24683175 25713864 25741863 26174835 26831475 27368514
27581463 35281746 35841726 36258174
八皇后问题共有12个解. 这12组独立解如图6-3所示。
(15863724) (16837425) (24683175) (25713864)
■□□□□□□□ ■□□□□□□□ □■□□□□□□ □■□□□□□□
□□□□■□□□ □□□□□■□□ □□□■□□□□ □□□□■□□□
□□□□□□□■ □□□□□□□■ □□□□□■□□ □□□□□□■□
□□□□□■□□ □□■□□□□□ □□□□□□□■ ■□□□□□□□
□□■□□□□□ □□□□□□■□ □□■□□□□□ □□■□□□□□
□□□□□□■□ □□□■□□□□ ■□□□□□□□ □□□□□□□■
□■□□□□□□ □■□□□□□□ □□□□□□■□ □□□□□■□□
□□□■□□□□ □□□□■□□□ □□□□■□□□ □□□■□□□□
(25741863) (26174835) (26831475) (27368514)
□■□□□□□□ □■□□□□□□ □■□□□□□□ □■□□□□□□
□□□□■□□□ □□□□□■□□ □□□□□■□□ □□□□□□■□
□□□□□□■□ ■□□□□□□□ □□□□□□□■ □□■□□□□□
□□□■□□□□ □□□□□□■□ □□■□□□□□ □□□□□■□□
■□□□□□□□ □□□■□□□□ ■□□□□□□□ □□□□□□□■
□□□□□□□■ □□□□□□□■ □□□■□□□□ □□□□■□□□
□□□□□■□□ □□■□□□□□ □□□□□□■□ ■□□□□□□□
□□■□□□□□ □□□□■□□□ □□□□■□□□ □□□■□□□□
(27581463) (35281746) (35841726) (36258174)
□■□□□□□□ □□■□□□□□ □□■□□□□□ □□■□□□□□
□□□□□□■□ □□□□■□□□ □□□□■□□□ □□□□□■□□
□□□□■□□□ □■□□□□□□ □□□□□□□■ □■□□□□□□
□□□□□□□■ □□□□□□□■ □□□■□□□□ □□□□■□□□
■□□□□□□□ ■□□□□□□□ ■□□□□□□□ □□□□□□□■
□□□■□□□□ □□□□□□■□ □□□□□□■□ ■□□□□□□□
□□□□□■□□ □□□■□□□□ □■□□□□□□ □□□□□□■□
□□■□□□□□ □□□□□■□□ □□□□□■□□ □□□■□□□□
图6-3 八皇后问题的12组独立解
细心的读者可能想到，12组独立解＋(12×7)个衍生解，总数似应为96，为什么ex6-51程序仅给出92个解呢？原因是第10组独立解{3,5,2,8,1,7,4,6}(参看图6-3)给出的棋局为中心对称图形，即旋转180°后形状不变。因此这组解实际上只能给出3个(而不是7个)不雷同的衍生解。八皇后问题解的个数可表示为11×8＋1×4＝92。
