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

1、算法大作業(yè)電子工程學(xué)院A.實(shí)驗(yàn)內(nèi)容在n×n格的棋盤上放置彼此不受攻擊的n個(gè)皇后，按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子，求解可以放置的方法種數(shù)。B.問題分析n后問題等于于在n×n格的棋盤上放置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è)問題包括了行，列，兩條對角線； 列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突； 行：當(dāng)?shù)趇行被某個(gè)皇后占領(lǐng)后，則同一行

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

3、在同一斜線上;兩種情況兩皇后都可相互攻擊，返回false表示不符合條件。bool Place(int k)int i;i=1;while(i<k)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;i<=n;i+)printf("%d,",xi);if(i%n=0)printf(");n");3) 回溯法搜索解空間v

4、oid NQueens(int n)int k=1;x1=0;while(k>0)xk+=1;while(xk<=n&&!Place(k)xk+=1;if(xk<=n)if(k=n)Print(x,n);elsek=k+1;xk=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,

5、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,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為例#include <stdio.h>#include<math.h>#define N 4 /* 定義棋盤大小 */static int sum; /* 當(dāng)前已找到解的個(gè)數(shù) */sta

6、tic int xN; int place(int 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; printf("第%d種解法:n", + sum); for (i = 0; i < N; i +) for (j = 0; j < N; j +) if (j = xi) printf("Q ");site

7、i=j+1; else printf("* "); printf("n"); printf("A%d(",sum); for(i = 0; i < N; i +) printf("%d,",sitei); printf(");"); printf("n");/* 回溯搜索解空間 */void backtrack() int k = 0; x0 = -1; while (k >= 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();printf("%d皇后有%d個(gè)解:n",N,sum); return 0;實(shí)驗(yàn)結(jié)果截圖：5. 流程圖通過算法老師布置的這次大作業(yè)，首先使我們更好地