八皇后与回溯法的研究课程论文

在一个8×8的棋盘里放置8个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。 〖问题分析〗(聿怀中学吕思博) 这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题： 1、冲突。包括行、列、两条对角线： （1）列：规定每一列放一个皇后，不会造成列上的冲突； （2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； （3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。 2、数据结构。 （1）解数组A。A[I]表示第I个皇后放置的列；范围：1..8 （2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8 （3）对角线冲突标记数组C、D。 C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7 D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16 〖算法流程〗 1、数据初始化。 2、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于0（未被占领）: 如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归； 如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。 3、当n>;8时，便一一打印出结果。 〖优点〗逐一测试标准答案，不会有漏网之鱼。 〖参考程序〗 ---------------------------------------------------------------------------- programtt; vara:array[1..8]ofinteger; b,c,d:array[-7..16]ofinteger; t,i,j,k:integer; procedureprint; begin t:=t+1; write(t,''); fork:=1to8dowrite(a[k],''); writeln; end; proceduretry(i:integer); varj:integer; begin forj:=1to8do{每个皇后都有8种可能位置} if(b[j]=0)and(c[i+j]=0)and(d[i-j]=0)then{判断位置是否冲突} begin a:=j;{摆放皇后} b[j]:=1;{宣布占领第J行} c[i+j]:=1;{占领两个对角线} d[i-j]:=1; ifi<8thentry(i+1){8个皇后没有摆完，递归摆放下一皇后} elseprint;{完成任务，打印结果} b[j]:=0;{回溯} c[i+j]:=0; d[i-j]:=0; end; end; begin fork:=-7to16do{数据初始化} begin b[k]:=0; c[k]:=0; d[k]:=0; end; try(1);{从第1个皇后开始放置} end. ========================================== 这是N皇后问题，看看吧： 在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。 const max=8; var i,j:integer; a:array[1..max] of 0..max; //放皇后数组 b:array[2..2*max] of boolean; // ‘/’对角线标志数组} c:array[-(max-1)..max-1] of boolean;// ‘\’对角线标志数组} col:array[1..max] of boolean; //列标志数组} total:integer; //统计总数} procedure output; //这里是输出过程 var i:integer; begin write('No.':4,'[',total+1:2,']'); for i:=1 to max do write(a[i]:3);write(' '); if (total+1) mod 2 =0 then writeln; inc(total); end; function ok(i,dep:integer):boolean; //判断第dep行第i列可放否？ begin ok:=false; if ( b[i+dep]=true) and ( c[dep-i]=true) {and (a[dep]=0)} and (col[i]=true) then ok:=true end; procedure try(dep:integer); var i,j:integer; begin for i:=1 to max do //每一行均有max种放法，对吧？xixi~~~~ if ok(i,dep) then begin a[dep]:=i; b[i+dep]:=false; // ‘/’对角线已放标志 c[dep-i]:=false; // ‘\’对角线已放标志 col[i]:=false; // 列已放标志 if dep=max then output else try(dep+1); // 递归下一层 a[dep]:=0; //取走皇后,回溯 b[i+dep]:=true; //恢复标志数组 c[dep-i]:=true; col[i]:=true; end; end; begin for i:=1 to max do begin a[i]:=0;col[i]:=true;end; for i:=2 to 2*max do b[i]:=true; for i:=-(max-1) to max-1 do c[i]:=true; total:=0; try(1); writeln('total:',total); end.

bool C[9];定义的是列标志，表示该列是否可以放皇后。bool L[17];表示的\这个对角线方向上的是否可以放皇后。bool R[17];表示的是/这个对角线方向上是否可以放皇后。你仔细看矩阵\这个方向和/这个方向上的下标是有规律的。q[i]=-1;多余没有用处可以去掉C[j]=true; L[i-j+Normalize]=true; R[i+j]=true;这就是回溯的关键，恢复标志位。另外你程序是4皇后，不是8皇后。

这个回溯有点乱，加我，我跟你慢慢讲解。或者你也可以看看我写的这个代码：#include <>#include <>#include <>int cells[64];/*存储摆放方案，一维数组视为二维棋盘*/int num=0;/*记录尝试次数*/int output()/*输出棋盘状态*/{ static int count=0;/*静态变量计录本次输出的编号*/ int t=0,m,n;/*辅助计算黑白格的选取*/ count++; printf("方案%d：\r\n",count); for(m=0;m<8;m++){ for(n=0;n<8;n++){ t++; if(cells[n+m*8]==0){/*没有皇后*/ t%2?printf("□"):printf("■");/*根据奇偶与否决定输出格子黑白*/ }else{/*有皇后*/ printf("★"); } } t++;/*偏移，使黑白格交错*/ printf("\r\n"); } if(count==30||count==60)system("pause"); return 0; }int ok(int i)/*递归判断第i行的落子可行性*/{ int k,j,t1,t2,r;/*临时变量，作用随机*/ for(k=0;k<8;k++){/*从行首开始向后轮流判断*/ r=0;num++;/*r存储是否存在冲突，非0则为冲突*/ for(j=0;j<8;j++){/*清空该行可能的棋子，避免由子过程返回后产生的冲突。*/ cells[j+i*8]=0; } for(j=0;j=0){/*斜线上仍有格子*/ if(cells[t1]){r=1;break;}/*斜向存在冲突*/ t1-=9;/*继续移动*/ } t2-=7;/*同理*/ while(t2%8!=0&&t2>=0){ if(cells[t2]){r=1;break;} t2-=7; } if(!r){/*没有发生冲突*/ cells[k+i*8]=1;/*确认落子*/ if(i<7){/*没有落完八个皇后*/ ok(i+1);/*继续在下一行寻找方案*/ }else{/*落子成功结束*/ output();/*输出棋盘状况*/ } } } return 0;}int main()/*应用程序入口，不解释*/{ int i;/*临时变量，用于初始化棋盘*/ double a,b,c;/*计时用*/ printf(Q); printf("什么？八皇后？小case，马上给出答案～～\r\n"); for(i=0;i<64;i++){/*棋盘初始化*/ cells[i]=0; } a=clock();/*开始时间*/ ok(0);/*运算*/ b=clock();/*结束时间*/ printf("\r\n回答完毕！\r\n"); c=(double)(b-a)/CLOCKS_PER_SEC;/*计算时间间隔*/ printf("经过%i次尝试，耗时%f秒，表示没有鸭梨……\r\n\r\n",num,c); return 0;}

这三个数组是bool类型的 用来判定行和列是否已经用过 可以搜索Matrix67 他有用位运算解的把皇后问题

以前每次遇到算法问题都是直接暴力求解，一直以为自己用的是暴力穷举法，现在学了回溯法，发现部分问题其实使用的是回溯法，而不是单纯的暴力穷举。

例如求解一个n皇后问题：

1.使用暴力穷举，由于没有两个皇后能够放在一列上，那么解向量一定是数1，2，····，n的一个排列（第一行n种放法，第二行n-1种，以此类推）。时间复杂度O(n!).

为什么是一维而不是两维？因为没有两个皇后能在同一列，所以只用行标志就可以表示出皇后的位置，简化了问题

2.回溯法，就等于是一个一个的试，从1到n，时间复杂度O(n^n),每一行n种放法，总共n行。

看起来回溯法要比暴力穷举差很多，但是实际上回溯法很多时候实际算法复杂度并没有暴力穷举高。比如4皇后问题中，仅需要341个可能节点中的27个节点就可以找到解，但是暴力穷举实际会慢很多。

换一个思路，比如第一个皇后放在了0位置，暴力穷举第二个皇后放在1位置，那么之后的皇后无论怎么放都是错误的，也就是(n-2)!个向量全部都是错误的，而回溯法面对这种问题，会在之前就直接抛弃这种情况，速度会快很多。不要问为什么暴力穷举为什么不学回溯法那样提前抛弃，因为它是 暴力穷举 （这还算优化过一次，不然直接O(n^n)）。

总而言之，回溯法并不需要得到所有情况，而且运行过程中会提前抛弃不合要求的情况，所以算法复杂度一般不会到最差的情况。