這幾天突然對八皇后問題很感興趣，準備自己動手實現它，從最笨的辦法一直到用圖論實現，展示出它的進化歷程。 每個程序段我都講的很細致。 這是第一篇：最笨的方法。歡迎探討。

By the way .八皇后有92種解法，這個程序都羅列出來了。

過幾天再用python寫個實現，估計代碼看起來會比C的實現漂亮多了。

運行結果如圖：

/** * The famous 8 queens problem. * * @file * @brief * The famous 8 queens problem. * @author Gary Gao <garygaowork@gmail.com> * @date 2011/06/24 * */ /* ** 約定：棋盤的坐標是行r0-r7,列c0-c7 */ #include <stdio.h> #define SUCCEEDED 0 #define FAILED -1 #define CHESSBD_WIDTH 8 void init_chessbd(); void show_chessbd(); void solve_8queens(); int test(int[],int, int[],int); int get_queen_pos(int); int chessbd[CHESSBD_WIDTH][CHESSBD_WIDTH]; /** * @brief main * */ int main(int argc,char* argv[]) { solve_8queens(); return 0; } /** * @brief 顯示棋盤 * */ void show_chessbd() { int i,j; for(j = 0 ; j < CHESSBD_WIDTH; j++){ if(j == 0){ printf("%8d",j); }else{ printf("%4d",j); } if(j == CHESSBD_WIDTH-1){ printf("/n"); } } for(i = 0 ; i < CHESSBD_WIDTH ; i++ ){ printf("%4d",i); for(j = 0 ; j < CHESSBD_WIDTH ; j++){ printf("%4d",chessbd[i][j]); } printf("/n/n"); } } /** * @brief 解八皇后問題的主要函數 * */ void solve_8queens() { int ret; int result = 0; int i; //Row int j; //Column int col_start; /* ** 行列占用標記，如果某行rX(列cY)已經擺放了皇后(即被占用)， ** 則row_marks[rX](或者col_marks[cY])置1. */ int row_marks[CHESSBD_WIDTH]={0}; //行占用標記 int col_marks[CHESSBD_WIDTH]={0}; //列占用標記 ret = SUCCEEDED; //初始化ret for( i = 0 ; i < CHESSBD_WIDTH ; i++){ /* **如果是第一次進入循環或者 **上一行(r_last)能夠成功找到皇后的位置,即上一次ret返回SUCCEEDED. **那么設置col_start = 0 ,從當前行(r_cur)行的第一列開始尋找皇后位置. */ if(ret == SUCCEEDED){ col_start = 0; } for(j = col_start; j < CHESSBD_WIDTH;j++){ //測試當前位置Current(i,j)是否滿足皇后擺放條件 ret = test(row_marks,i,col_marks,j); if(ret == SUCCEEDED){ chessbd[i][j] = 1; { //設置占用標記 row_marks[i] = 1; //設置第i行已經擺放了皇后 col_marks[j] = 1; //設置第j列已經擺放了皇后 } /* **以下包括在if語句塊中的code是為找出所有解法而準備的。 **思路: ** 如果棋盤的最后一行條件測試成功(ret=SUCCEEDED),說明找到了一種解法. ** 每當找出一個解法，就顯示此解法,然后設置此解"不成立", ** 從c_cur+1開始繼續尋找新的解法。 */ if( i == CHESSBD_WIDTH-1){ printf("/n@Found a solution,NO.%d/n/n",++result); show_chessbd(); //因為要尋找新的解法，所以剛才的標記要清除. chessbd[i][j] = 0; { //設置占用標記 row_marks[i] = 0; col_marks[j] = 0; } ret = FAILED; }else{ break; } } } /* *當 ret == FAILED && j == CHESSBD_WIDTH 且i == 0 時，所有的解法就尋找完畢了 *不需要繼續運行了,直接跳出大循環. *否則，再往下就會出現段錯誤.(原因:數組下標越界) */ if(ret == FAILED && j == CHESSBD_WIDTH &&i == 0){ break; } /* **Go back one step. **如果當前行(r_cur)的最后一列(c7)的條件測試仍然不成立， **則退回到上一行(r_last)，繼續在上一行尋找新的合適皇后擺放位置。 */ if( ret == FAILED && j == CHESSBD_WIDTH ){ //獲得上一行(r_last) queen所在的列坐標 col_start = get_queen_pos(i-1); //撤銷[上一行]占用標記 { row_marks[i-1] = 0; col_marks[col_start] = 0; chessbd[i-1][col_start] = 0; } //定位上一個queen. //設置上一行(r_last)皇后位置的下一列(c_next)為新的測試位置 col_start++; //因為在此輪循環結束時for循環會自動i++ //所以此處需i-2才能跳轉到上一行(r_last) i = i-2; } } } /** * @brief 測試給定的position是否滿足擺放皇后的條件. * * @param[in] row_marks - 行占用標記. * @param[in] r_num - 被測試的Row positon. * @param[in] col_marks - 列占用標記. * @param[in] c_num - 被測試的Column positon. * @return - 返回SUCCEEDED如果滿足擺放皇后的條件.否則返回FAILED. */ int test( int row_marks[],int r_num, int col_marks[],int c_num ) { int ret; int i,j; ret = SUCCEEDED; //test row if(row_marks[r_num] == 1 ){ ret = FAILED; } //test column if(col_marks[c_num] == 1 ){ ret = FAILED; } //test主對角線 i = r_num-1; j = c_num-1; for( i,j ; i >= 0 && j >= 0 ;i--,j--){ if(chessbd[i][j] == 1){ ret = FAILED; break; } } //test副對角線 i = r_num-1; j = c_num+1; for(i,j ; i >= 0 && j < CHESSBD_WIDTH;i--,j++){ if(chessbd[i][j] == 1){ ret = FAILED; break; } } return ret; } /** * @brief Get the position of queen in the specified row * * @param[in] row_num - Row position. * @return - Column position of the queen in the specified row. */ int get_queen_pos(int row_num) { int col; int j; //chessbd for( j = 0 ; j < CHESSBD_WIDTH; j++){ if( chessbd[row_num][j] == 1){ col = j; break; } } return col; } /* Log20110622.1: 檢測符合八皇后的條件的方法有兩種，一種是最笨的掃描檢測方法，另一種是標記檢測方法。 目前行列檢測使用的是標記檢測方法，而主副對角線序列使用的是笨方法。[因為我還沒學會矩陣的內容] Log20110622.2: 找出所有解法后，出現段錯誤，未知原因。 對debug進行了分級DEBUG_A,DEBUG_B,DEBUG_C */ /* TASK20110622: Done 找出八皇后的所有解法——92種 TASK20110622: Done 段錯誤已經修復，段錯誤是數組越界訪問引起的。 優化八皇后解法的代碼 使用其他編程思路解決八皇后問題(參考,http://baike.baidu.com/view/622604.htm,) TASK20110624: Done 為程序添加簡單易懂的注釋 學習到的新技巧： gcc命令中定義宏使用—D選項. */

八皇后問題的進化(1)-最基礎的實現