數(shù)據(jù)結(jié)構(gòu)常見問題：12單元25 八皇后問題

1、數(shù)據(jù)結(jié)構(gòu)課程常見問題 -單元25 八皇后問題1八皇后問題？解析：要求在88 格的國際象棋棋盤上擺放8 個皇后，使其不能互相攻擊。由于皇后的走棋法是可以橫走或直走或走斜線，每次走任意格數(shù)，所以要求這八個皇后中的任意兩個都不處于同一行、同一列或同一斜線上。問有多少種擺法？#include#define N 8 /*設置最大皇后數(shù)*/int padN; /*聲明數(shù)組，索引值為行號，數(shù)據(jù)值為列號*/int count; /*聲明計數(shù)器，記錄找到解的個數(shù)*/*-*/* 放置皇后的遞歸函數(shù) */*-*/int put_queen(int x) int i,j; if(x=N) /*終止條件*/ for(i

2、=0;iN;i+) /*通過遍歷輸出解*/ for(j=0;jN;j+) if(padi=j) /*是皇后*/ printf(“*“); else /*不是皇后*/ printf(“0“); printf(“n“); /*換行*/ count+; /*解的個數(shù)加1*/ printf(“Press any key to look for the next KEY:“); getchar(); /*按任意鍵繼續(xù)求解*/ else for(i=0;iN;i+) if(place(x,i) /*檢查是否可放置皇后*/ padx=i; put_queen(x+1); /*-*/* 檢查皇后是否相互攻擊

3、*/*-*/int place(int r,int c) int i; if(r=0) /*第一行可以隨意放置*/ return 1; for(i=0;ir;i+) /*判斷是否與前邊的皇后相互攻擊*/ if(c=padi | (c+r)=i+padi | (c-r)=padi-i) return 0; return 1;/*-*/* 主程序：遞歸法解八皇后問題 */*-*/main() clrscr(); /*清屏*/ count=0; /*解的個數(shù)置零*/ put_queen(0); /*調(diào)用遞歸函數(shù)*/ printf(“There are %d keys.n“,count); /*輸出解

4、的個數(shù)*/代碼2：遞歸實現(xiàn)n皇后問題算法分析：數(shù)組a、b、c分別用來標記沖突，a數(shù)組代表列沖突，從a0a7代表第0列到第7列，如果某列上已經(jīng)有皇后，則為1，否則為0；數(shù)組代表主對角線沖突，為bi-j+7，即從b0b14，如果某條主對角線上已經(jīng)有皇后，則為1，否則為0；數(shù)組c代表從對角線沖突，為ci+j，即從c0c14，如果某條從對角線上已經(jīng)有皇后，則為1，否則為0。程序如下：#include static char Queen88;static int a8;static int b15;static int c15;static int iQueenNum=0; /記錄總的棋盤狀態(tài)數(shù)void

5、 qu(int i); /參數(shù)i代表行int main()int iLine,iColumn;/棋盤初始化，空格為*，放置皇后的地方為for(iLine=0;iLine8;iLine+)aiLine=0; /列標記初始化，表示無列沖突for(iColumn=0;iColumn8;iColumn+)QueeniLineiColumn=*;/主、從對角線標記初始化，表示沒有沖突for(iLine=0;iLine15;iLine+)biLine=ciLine=0;qu(0);return 0;void qu(int i)int iColumn;for(iColumn=0;iColumn8;iColu

6、mn+)if(aiColumn=0&bi-iColumn+7=0&ci+iColumn=0) /如果無沖突QueeniiColumn=; /放皇后aiColumn=1; /標記，下一次該列上不能放皇后bi-iColumn+7=1; /標記，下一次該主對角線上不能放皇后ci+iColumn=1; /標記，下一次該從對角線上不能放皇后if(i7) qu(i+1); /如果行還沒有遍歷完，進入下一行else /否則輸出/輸出棋盤狀態(tài)int iLine,iColumn;printf(第%d種狀態(tài)為：n,+iQueenNum);getchar();for(iLine=0;iLine8;iLine+)for(iColumn=0;iColumn8;iColumn+)printf(%c ,QueeniLineiColumn);printf(n);pri