0 前言

還有一年就要畢業(yè)了陨闹，希望自己每天都能夠刷幾題墩邀，為找工作做好準(zhǔn)備搁料。

1 問(wèn)題介紹

八皇后問(wèn)題是一個(gè)以國(guó)際象棋為背景的問(wèn)題：如何能夠在8×8的國(guó)際象棋棋盤(pán)上放置八個(gè)皇后凉驻，使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后面徽？為了達(dá)到此目的艳丛，任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線(xiàn)上趟紊。八皇后問(wèn)題可以推廣為更一般的n皇后擺放問(wèn)題：這時(shí)棋盤(pán)的大小變?yōu)?em>n×n氮双，而皇后個(gè)數(shù)也變成n。當(dāng)且僅當(dāng)n = 1或n ≥ 4時(shí)問(wèn)題有解

八皇后擺法示例

2 解題思路

可以用到遞歸的思想饭入，我們可以把問(wèn)題用函數(shù)_solve(row)來(lái)表示嵌器，其中，參數(shù)row表示前0~row-1的皇后都滿(mǎn)足要求谐丢，此時(shí)爽航，問(wèn)題可以拆分成兩個(gè)

• 放一個(gè)皇后在第row行的棋盤(pán)，使得他與前面的0~row-1行放的皇后都不沖突
• 遞歸求解_solve(row+1)

3 代碼講解

主函數(shù)

_solve(0);//從第0行開(kāi)始擺放

用上面的思路暴力求解

// 參數(shù)表示第row行前面都已經(jīng)擺好了
            void _solve(int row) {  
                int i;
                for (i=0;i<8;i++) {
                    board[row][i] = '1';
                    // 判斷當(dāng)前位置是否可以擺
                    if (check(row, i)) {
                        if (row == 7) print();
                        else _solve(row+1);
                    }
                    //同一行下一列進(jìn)行比較
                    board[row][i] = '0';    
                }

判斷當(dāng)前擺放的皇后與前面已經(jīng)擺好的皇后有無(wú)沖突

bool check(int row, int col) {
                int i,j;

                // 棋子不能在同一列
                for (i=0;i<row;i++) {
                    if (board[i][col] == '1') {
                        return false;
                    }
                }

                // 棋子不能在左上角
                i = row-1, j = col-1;
                while (i>=0 && j >=0) {
                    if (board[i][j] == '1') {
                        return false;
                    }
                    i--;
                    j--;
                }
                // 棋子不能再右上角
                i = row-1, j = col+1;
                while (i>=0 && j <8) {
                    if (board[i][j] == '1') {
                        return false;
                    }
                    i--;
                    j++;
                }

                return true;
            }

完整代碼

namespace alg {
    class Queen8 {
        private:
            // 建立一個(gè)8*8棋盤(pán)
            char board[8][8];
            // 記錄有多少種擺法
            int cnt;
        public:
            void solve() {
                memset(board, '0', sizeof(board));
                cnt = 0;
                _solve(0);//從第0行開(kāi)始擺放
            }
        private:
        // 參數(shù)表示第row行前面都已經(jīng)擺好了
            void _solve(int row) {  
                int i;
                for (i=0;i<8;i++) {
                    board[row][i] = '1';
                    // 判斷當(dāng)前位置是否可以擺
                    if (check(row, i)) {
                        if (row == 7) print();
                        else _solve(row+1);
                    }
                    //同一行下一列進(jìn)行比較
                    board[row][i] = '0';    
                }
            }

            void print() {
                printf("chessboard: %d\n",++cnt);
                int i,j;
                for (i=0;i<8;i++) {
                    for (j=0;j<8;j++) {
                        printf("%c ", board[i][j]);
                    }
                    printf("\n");
                }
            }

            bool check(int row, int col) {
                int i,j;

                // 棋子不能在同一列
                for (i=0;i<row;i++) {
                    if (board[i][col] == '1') {
                        return false;
                    }
                }

                // 棋子不能在左上角
                i = row-1, j = col-1;
                while (i>=0 && j >=0) {
                    if (board[i][j] == '1') {
                        return false;
                    }
                    i--;
                    j--;
                }
                // 棋子不能再右上角
                i = row-1, j = col+1;
                while (i>=0 && j <8) {
                    if (board[i][j] == '1') {
                        return false;
                    }
                    i--;
                    j++;
                }

                return true;
            }
    };
}