八皇后問題遞歸算法 + Pascal 程序

cinc

[這個(gè)貼子最后由cinc在 2002/09/11 01:58pm 編輯]

在網(wǎng)上找到的一個(gè) 八皇后問題的 pascal 解法。可以參考參考：
八皇后問題
--------------------------------------------------------------------------------

〖問題描述〗
在一個(gè)８×８的棋盤里放置８個(gè)皇后，要求每個(gè)皇后兩兩之間不相"沖"（在每一橫列豎列斜列只有一個(gè)皇后）。

〖問題分析〗(聿懷中學(xué) 呂思博)
這道題可以用遞歸循環(huán)來做，分別一一測試每一種擺法，直到得出正確的答案。主要解決以下幾個(gè)問題：
1、沖突。包括行、列、兩條對(duì)角線：
（1）列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突；
（2）行：當(dāng)?shù)贗行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以I為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)；
（3）對(duì)角線：對(duì)角線有兩個(gè)方向。在同一對(duì)角線上的所有點(diǎn)（設(shè)下標(biāo)為(i,j)），要么(i+j)是常數(shù)，要么(i-j)是常數(shù)。因此，當(dāng)?shù)贗個(gè)皇后占領(lǐng)了第J列后，要同時(shí)把以(i+j)、(i-j)為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。
2、數(shù)據(jù)結(jié)構(gòu)。
（1）解數(shù)組A。A[I]表示第I個(gè)皇后放置的列；范圍：1..8
（2）行沖突標(biāo)記數(shù)組B。B[I]=0表示第I行空閑；B[I]=1表示第I行被占領(lǐng)；范圍：1..8
（3）對(duì)角線沖突標(biāo)記數(shù)組C、D。
C[I-J]=0表示第（I-J）條對(duì)角線空閑；C[I-J]=1表示第（I-J）條對(duì)角線被占領(lǐng)；范圍：-7..7
D[I+J]=0表示第（I+J）條對(duì)角線空閑；D[I+J]=1表示第（I+J）條對(duì)角線被占領(lǐng)；范圍：2..16

〖算法流程〗
１、數(shù)據(jù)初始化。
２、從n列開始擺放第n個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求），先測試當(dāng)前位置(n,m)是否等于０（未被占領(lǐng)）:
如果是，擺放第n個(gè)皇后，并宣布占領(lǐng)(記得要橫列豎列斜列一起來哦)，接著進(jìn)行遞歸；
如果不是，測試下一個(gè)位置(n,m+1)，但是如果當(dāng)n<=8,m=8時(shí)，卻發(fā)現(xiàn)此時(shí)已經(jīng)無法擺放時(shí)，便要進(jìn)行回溯。
３、當(dāng)n>;8時(shí)，便一一打印出結(jié)果。


〖優(yōu)點(diǎn)〗逐一測試標(biāo)準(zhǔn)答案，不會(huì)有漏網(wǎng)之魚。

〖參考程序〗queen.pas
----------------------------------------------------------------------------
program tt&#59;
var a:array [1..8] of integer&#59;
   b,c,d:array [-7..16] of integer&#59;
   t,i,j,k:integer&#59;
procedure print&#59;
begin
     t:=t+1&#59;
     write(t,'       ')&#59;
     for k:=1 to 8 do write(a[k],'   ')&#59;
     writeln&#59;
end&#59;

procedure try(i:integer)&#59;
var j:integer&#59;
begin
    for j:=1 to 8 do {每個(gè)皇后都有8種可能位置}
         if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判斷位置是否沖突}
         begin
               a:=j&#59; {擺放皇后}
               b[j]:=1&#59; {宣布占領(lǐng)第J行}
               c[i+j]:=1&#59; {占領(lǐng)兩個(gè)對(duì)角線}
               d[i-j]:=1&#59;
               if i<8 then try(i+1) {8個(gè)皇后沒有擺完，遞歸擺放下一皇后}
                       else print&#59;  {完成任務(wù)，打印結(jié)果}
              b[j]:=0&#59;    {回溯}
              c[i+j]:=0&#59;
              d[i-j]:=0&#59;
         end&#59;
end&#59;
begin
    for k:=-7 to 16 do {數(shù)據(jù)初始化}
    begin
         b[k]:=0&#59;
         c[k]:=0&#59;
         d[k]:=0&#59;
    end&#59;
    try(1)&#59;{從第1個(gè)皇后開始放置}
end.
----------------------------------------------------------------------------

cinc

呵呵，有誰愿意，可以把他用 Java 實(shí)現(xiàn)看看。。。：）