這幾天突然對(duì)八皇后問(wèn)題很感興趣，準(zhǔn)備自己動(dòng)手實(shí)現(xiàn)它，從最笨的辦法一直到用圖論實(shí)現(xiàn)，展示出它的進(jìn)化歷程。 每個(gè)程序段我都講的很細(xì)致。 這是第一篇：最笨的方法。歡迎探討。

By the way .八皇后有92種解法，這個(gè)程序都羅列出來(lái)了。

過(guò)幾天再用python寫(xiě)個(gè)實(shí)現(xiàn)，估計(jì)代碼看起來(lái)會(huì)比C的實(shí)現(xiàn)漂亮多了。

運(yùn)行結(jié)果如圖：

/** * The famous 8 queens problem. * * @file * @brief * The famous 8 queens problem. * @author Gary Gao <garygaowork@gmail.com> * @date 2011/06/24 * */ /* ** 約定：棋盤(pán)的坐標(biāo)是行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 顯示棋盤(pán) * */ 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 解八皇后問(wèn)題的主要函數(shù) * */ void solve_8queens() { int ret; int result = 0; int i; //Row int j; //Column int col_start; /* ** 行列占用標(biāo)記，如果某行rX(列cY)已經(jīng)擺放了皇后(即被占用)， ** 則row_marks[rX](或者col_marks[cY])置1. */ int row_marks[CHESSBD_WIDTH]={0}; //行占用標(biāo)記 int col_marks[CHESSBD_WIDTH]={0}; //列占用標(biāo)記 ret = SUCCEEDED; //初始化ret for( i = 0 ; i < CHESSBD_WIDTH ; i++){ /* **如果是第一次進(jìn)入循環(huán)或者 **上一行(r_last)能夠成功找到皇后的位置,即上一次ret返回SUCCEEDED. **那么設(shè)置col_start = 0 ,從當(dāng)前行(r_cur)行的第一列開(kāi)始尋找皇后位置. */ if(ret == SUCCEEDED){ col_start = 0; } for(j = col_start; j < CHESSBD_WIDTH;j++){ //測(cè)試當(dāng)前位置Current(i,j)是否滿足皇后擺放條件 ret = test(row_marks,i,col_marks,j); if(ret == SUCCEEDED){ chessbd[i][j] = 1; { //設(shè)置占用標(biāo)記 row_marks[i] = 1; //設(shè)置第i行已經(jīng)擺放了皇后 col_marks[j] = 1; //設(shè)置第j列已經(jīng)擺放了皇后 } /* **以下包括在if語(yǔ)句塊中的code是為找出所有解法而準(zhǔn)備的。 **思路: ** 如果棋盤(pán)的最后一行條件測(cè)試成功(ret=SUCCEEDED),說(shuō)明找到了一種解法. ** 每當(dāng)找出一個(gè)解法，就顯示此解法,然后設(shè)置此解"不成立", ** 從c_cur+1開(kāi)始繼續(xù)尋找新的解法。 */ if( i == CHESSBD_WIDTH-1){ printf("/n@Found a solution,NO.%d/n/n",++result); show_chessbd(); //因?yàn)橐獙ふ倚碌慕夥?，所以剛才的?biāo)記要清除. chessbd[i][j] = 0; { //設(shè)置占用標(biāo)記 row_marks[i] = 0; col_marks[j] = 0; } ret = FAILED; }else{ break; } } } /* *當(dāng) ret == FAILED && j == CHESSBD_WIDTH 且i == 0 時(shí)，所有的解法就尋找完畢了 *不需要繼續(xù)運(yùn)行了,直接跳出大循環(huán). *否則，再往下就會(huì)出現(xiàn)段錯(cuò)誤.(原因:數(shù)組下標(biāo)越界) */ if(ret == FAILED && j == CHESSBD_WIDTH &&i == 0){ break; } /* **Go back one step. **如果當(dāng)前行(r_cur)的最后一列(c7)的條件測(cè)試仍然不成立， **則退回到上一行(r_last)，繼續(xù)在上一行尋找新的合適皇后擺放位置。 */ if( ret == FAILED && j == CHESSBD_WIDTH ){ //獲得上一行(r_last) queen所在的列坐標(biāo) col_start = get_queen_pos(i-1); //撤銷[上一行]占用標(biāo)記 { row_marks[i-1] = 0; col_marks[col_start] = 0; chessbd[i-1][col_start] = 0; } //定位上一個(gè)queen. //設(shè)置上一行(r_last)皇后位置的下一列(c_next)為新的測(cè)試位置 col_start++; //因?yàn)樵诖溯喲h(huán)結(jié)束時(shí)for循環(huán)會(huì)自動(dòng)i++ //所以此處需i-2才能跳轉(zhuǎn)到上一行(r_last) i = i-2; } } } /** * @brief 測(cè)試給定的position是否滿足擺放皇后的條件. * * @param[in] row_marks - 行占用標(biāo)記. * @param[in] r_num - 被測(cè)試的Row positon. * @param[in] col_marks - 列占用標(biāo)記. * @param[in] c_num - 被測(cè)試的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主對(duì)角線 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副對(duì)角線 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: 檢測(cè)符合八皇后的條件的方法有兩種，一種是最笨的掃描檢測(cè)方法，另一種是標(biāo)記檢測(cè)方法。 目前行列檢測(cè)使用的是標(biāo)記檢測(cè)方法，而主副對(duì)角線序列使用的是笨方法。[因?yàn)槲疫€沒(méi)學(xué)會(huì)矩陣的內(nèi)容] Log20110622.2: 找出所有解法后，出現(xiàn)段錯(cuò)誤，未知原因。 對(duì)debug進(jìn)行了分級(jí)DEBUG_A,DEBUG_B,DEBUG_C */ /* TASK20110622: Done 找出八皇后的所有解法——92種 TASK20110622: Done 段錯(cuò)誤已經(jīng)修復(fù)，段錯(cuò)誤是數(shù)組越界訪問(wèn)引起的。 優(yōu)化八皇后解法的代碼 使用其他編程思路解決八皇后問(wèn)題(參考,http://baike.baidu.com/view/622604.htm,) TASK20110624: Done 為程序添加簡(jiǎn)單易懂的注釋 學(xué)習(xí)到的新技巧： gcc命令中定義宏使用—D選項(xiàng). */

八皇后問(wèn)題的進(jìn)化(1)-最基礎(chǔ)的實(shí)現(xiàn)