我的思路是，先用遞歸函數找到一種解法。然后再用它找出所有的解法。這篇blog中是找出一種解法的基礎遞歸版本。

除了遞歸函數外，大部分函數沿用的是 《八皇后最基礎實現》 中的內容，比如條件測試函數，棋盤 顯示函數，因為它們不需要太多的“進化”。

運行結果如圖：

/** * The famous 8 queens problem. * * @file * @brief * The famous 8 queens problem. * @author Gary Gao <garygaowork@gmail.com> * @date 2011/06/26 * */ /* ** 約定：棋盤的坐標是行r0-r7,列c0-c7 */ #include <stdio.h> #define SUCCEEDED 0 #define FAILED -1 #define CHESSBD_WIDTH 8 //#define DEBUG_A void show_chessbd(); int put_queen(int); int search_next(int,int[],int[]); int test(int[],int,int[],int); int get_queen_pos(int); int chessbd[CHESSBD_WIDTH][CHESSBD_WIDTH]; int row_marks[CHESSBD_WIDTH]; int col_marks[CHESSBD_WIDTH]; /** * @brief main * */ int main(int argc,char* argv[]) { put_queen(0); show_chessbd(); return 0; } /** * @brief 解決八皇后問題的遞歸函數 * * @param[in] r_pos - 指定從第r_pos行尋找. * @return - 返回SUCCEEDED如果能夠成功在當前行(r_pos)擺放皇后.否則返回FAILED. */ int put_queen(int r_pos) { int ret; int search_ret ; int put_ret; if(r_pos == CHESSBD_WIDTH){ ret = SUCCEEDED; //基本 }else{ search_ret = search_next(r_pos,row_marks,col_marks); put_ret = FAILED; while(search_ret == SUCCEEDED && put_ret == FAILED){ put_ret = put_queen(r_pos+1); if(put_ret == FAILED){ search_ret = search_next(r_pos,row_marks,col_marks); }else{ //put_ret == SUCCEEDED ret = SUCCEEDED; break; } } if(search_ret == FAILED){ //程序運行到這里，說明在當前行(r_pos)沒有找到擺放皇后的位置. ret = FAILED; } } #ifdef DEBUG_A show_chessbd(); printf("@Debug:/t/nsearch_ret:%4d,put_ret:%4d,r_pos:%4d,ret:%4d",search_ret,put_ret,r_pos,ret); getchar(); #endif return ret; } /** * @brief 擺放皇后——在指定行尋找下一個可以擺放皇后的位置,同時在找到后設置占用標記 * * @param[in] r_num - 被測試的Row positon. * @param[in] row_marks - 行占用標記. * @param[in] col_marks - 列占用標記. * @return - 返回SUCCEEDED如果能夠成功擺放皇后.否則返回FAILED. */ int search_next(int r_pos,int row_marks[],int col_marks[] ) { int j; int c_pos; int test_ret = FAILED; //先撤銷上次的標記 c_pos = get_queen_pos(r_pos); if(chessbd[r_pos][c_pos] == 1) { chessbd[r_pos][c_pos] = 0; row_marks[r_pos] = 0; col_marks[c_pos] = 0; // c_pos++; } //然后尋找當前行(r_pos)新的皇后擺放位置 for( j = c_pos ; j< CHESSBD_WIDTH ; j++ ){ test_ret = test(row_marks,r_pos,col_marks,j ); if(test_ret == SUCCEEDED){ c_pos = j; break; } } //如果有滿足條件(即可以擺放皇后)，設置皇后占用標記 if(test_ret == SUCCEEDED){ chessbd[r_pos][c_pos] = 1; row_marks[r_pos] = 1; col_marks[c_pos] = 1; } return test_ret; } /** * @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 測試給定的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 col = 0; for( j = 0 ; j < CHESSBD_WIDTH; j++){ if( chessbd[row_num][j] == 1){ col = j; break; } } return col; } /** * Log20110626: * 用遞歸改寫八皇后問題，找到一種解法。 * */ /* * Task20110626: * 改寫程序，找出所有的解法。 * 添加注釋 * 變量定義時的初始值（全局變量，局部變量）問題，因為一直不明晰，經常釀成大錯。 */

八皇后問題的進化(2)-用遞歸函數實現