最佳答案

“八皇后”問題遞歸法求解 (Pascal語言) 八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，后來有人用圖論的方法解出92種結果。現代教學中，把八皇后問題當成一個經典遞歸算法例題。 算法分析：數組a、b、c分別用來標記沖突，a數組代表列沖突，從a[0]~a[7]代表第0列到第7列，如果某列上已經有皇后，則為1，否則為0；數組b代表主對角線沖突，為b[i-j+7]，即從b[0]~b[14]，如果某條主對角線上已經有皇后，則為1，否則為0；數組c代表從對角線沖突，為c[i+j]，即從c[0]~c[14]，如果某條從對角線上已經有皇后，則為1，否則為0；另優化：第一個皇后在1~4格，最后*2，即為總解數 } program queens; var a:array [1..8] of integer; b,c,d:array [-7..16] of integer; t,i,j,k:integer; procedure print; begin t:=t+1; write(t,': '); for k:=1 to 8 do write(a[k],' '); writeln; end; procedure try(i:integer); var j:integer; begin for j:=1 to 8 do {每個皇后都有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; if i<8 then try(i+1) {8個皇后沒有擺完，遞歸擺放下一皇后} else print; {完成任務，打印結果} b[j]:=0; {回溯} c[i+j]:=0; d[i-j]:=0; end; end; begin fillchar(a,sizeof(a),0); {初始化數組} fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); try(1);{從第1個皇后開始放置} end. “八皇后”問題遞歸法求解 (C語言) ＃i nclude "stdio.h" static char Queen[8][8]; static int a[8]; static int b[15]; static int c[15]; static int iQueenNum=0; //記錄總的棋盤狀態數 void qu(int i); //參數i代表行 int main() { int iLine,iColumn; //棋盤初始化，空格為*，放置皇后的地方為@ for(iLine=0;iLine<8;iLine++) { a[iLine]=0; //列標記初始化，表示無列沖突 for(iColumn=0;iColumn<8;iColumn++) Queen[iLine][iColumn]='*'; } //主、從對角線標記初始化，表示沒有沖突 for(iLine=0;iLine<15;iLine++) b[iLine]=c[iLine]=0; qu(0); return 0; } void qu(int i) { int iColumn; for(iColumn=0;iColumn<8;iColumn++) { if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0) //如果無沖突 { Queen[iColumn]='@'; //放皇后 a[iColumn]=1; //標記，下一次該列上不能放皇后 b[i-iColumn+7]=1; //標記，下一次該主對角線上不能放皇后 c[i+iColumn]=1; //標記，下一次該從對角線上不能放皇后 if(i<7) qu(i+1); //如果行還沒有遍歷完，進入下一行 else //否則輸出 { //輸出棋盤狀態 int iLine,iColumn; printf("第%d種狀態為：
",++iQueenNum); for(iLine=0;iLine<8;iLine++) { for(iColumn=0;iColumn2)this.width=screen.width/2" vspace=2 border=0>; } printf("

"screen.width/2)this.width=screen.width/2" vspace=2 border=0>; } //如果前次的皇后放置導致后面的放置無論如何都不能滿足要求，則回溯，重置 Queen[iColumn]='*'; a[iColumn]=0; b[i-iColumn+7]=0; c[i+iColumn]=0; } } } 八皇后的c語言解法： #include #include #include int n,k,a[20],num=0; int attack(int k){ int flag=0; int i=1; while ((i");} else { for (i=1;i"); getch(); }

回答者：wd1000062016-06-21 00:00