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

在一个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.