N皇后問題實(shí)驗(yàn)報(bào)告

1、算法大作業(yè)電子工程學(xué)院1B3JA. 實(shí)驗(yàn)內(nèi)容在nx n格的棋盤上放置彼此不受攻擊的n個(gè)皇后，按照國(guó)際象棋的規(guī) 貝皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子，求解可以 放置的方法種數(shù)。B. 問題分析n后問題等于于在nxn格的棋盤上放置n個(gè)皇后，任何2個(gè)皇后不放 在同一行或同一列或同一斜線上。即規(guī)定每一列放一個(gè)皇后，不會(huì)造成列 上的沖突；當(dāng)?shù)趇行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再 放皇后，要把以i為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。C. 算法設(shè)計(jì)1. 解決沖突問題：這個(gè)問題包括了行，列，兩條對(duì)角線； 列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突； 行：當(dāng)?shù)趇行被某個(gè)皇后占領(lǐng)后，則同一

2、行上的所有空格都不能再放皇 后，要把以i為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)；對(duì)角線：對(duì)角線有兩個(gè)方向。在這我把這兩條對(duì)角線稱為：主對(duì)角線和 從對(duì)角線。在同一對(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ì)因?yàn)?n 皇后問題，從 n 大于 11 開始求解過程耗時(shí)就很長(zhǎng)，所以定義 x 數(shù)組的最大值MAXNUM=；0!P最大可解決30皇后問題。1) 判斷當(dāng)前位置是否可放置皇后上;abs(xi-xk)=abs(i-k)皇后 k 在第 k 行第 xk 列時(shí)， xi=x

3、k 時(shí)，兩皇后在同一列 時(shí)，兩皇后在同一斜線上 ; 兩種情況兩皇后 都可相互攻擊，返回 false 表示不符合條件。bool Place(int k)int i;i=1;while(ik)if(xi=xk|abs(xi-xk)=abs(i-k) return false;i=i+1;return true;2) 輸出當(dāng)前解void Print(int x,int n)num+;printf(第dt 種解法:(,num);for(int i=1;i0)xk+=1;while(xk=n&!Place(k) xk+=1;if(xk=n)if(k=n)Prin t(x, n); elsek=k+1;x

4、k=0;回溯至上一行;/ elsek-；3. 實(shí)驗(yàn)結(jié)果及分析 n皇后問題解的情況皇后的個(gè) 數(shù)問題的解N=1X=(1)N=2無解N=3無解N=4X1=(2,4,1,3); X2=(3,1,4,2)N=5X1=(1,3,5,2,4); X2=(1,4,2,5,3); X3=(2,4,1,3,5);X4=(2,5,3,1,4)；X5=(3,1,4,2,5); X6=(3,5,2,4,1); X7=(4,1,3,5,2);X8=(4,2,5,3,1)；X9=(5,2,4,1,3); X10=(5,3,1,4,2)N=6X1=(2,4,6,1,3,5);X2=(3,6,2,5,1,4);X3=(4,1,

5、5,2,6,3);X4=(5,3,1,6,4,2)N=740個(gè)解N=892個(gè)解4.實(shí)驗(yàn)程序隨著N的增大，解的個(gè)數(shù)增多，以 N=4為例#i nclude #in clude#define N 4 /*定義棋盤大小*/static int sum; /*當(dāng)前已找到解的個(gè)數(shù)*/static int xN;int p lace(i nt k)int j;for (j = 0; j k; j +)if (xj = xk | abs(j - k) = abs(xj - xk) return 0;return 1;/* 打印棋局 */ void chessboard()int i,j;int siteN;p

6、rintf(第(種解法:n, + sum);for (i = 0; i N; i +) for (j = 0; j N; j +)if (j = xi) printf(Q );sitei=j+1; else printf(* );printf(n);printf(A%d(,sum);for(i = 0; i = 0) xk += 1; /* 向右移一列 */ /* 向右移至出最右列或可以放置皇后的列 while (xk N) & !(place(k) xk += 1; if (xk N) /*向右移未移出棋盤 */if (k = N - 1) chessboard(); /*/已移至最后一行 */else x+ k = -1; /* 向下移一行 else k -; /*回溯到上一行 */int main(void)*/backtrack();prin tf(%d皇后有 d 個(gè)解:n,N,sum);return 0;3/ 6實(shí)驗(yàn)結(jié)果截圖:第1種解法：* Q * 4C* * QQ -H -K- -H 來 M q M第2種幅= * Q *Q * * * * Q* Q * 4皇后有2個(gè)解=Piess any key to continue5.流程圖D. 心得體會(huì)通過算法老師布置的這次大作業(yè)，首先使我們更好地理解皇后問題和回溯法的 原理；其次，在作業(yè)過程中遇到的困難，使我們