0 前言

还有一年就要毕业了，希望自己每天都能够刷几题，为找工作做好准备。

1 问题介绍

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解

八皇后摆法示例

2 解题思路

可以用到递归的思想，我们可以把问题用函数_solve(row)来表示，其中，参数row表示前0~row-1的皇后都满足要求，此时，问题可以拆分成两个

• 放一个皇后在第row行的棋盘，使得他与前面的0~row-1行放的皇后都不冲突
• 递归求解_solve(row+1)

3 代码讲解

主函数

_solve(0);//从第0行开始摆放

用上面的思路暴力求解

// 参数表示第row行前面都已经摆好了
            void _solve(int row) {  
                int i;
                for (i=0;i<8;i++) {
                    board[row][i] = '1';
                    // 判断当前位置是否可以摆
                    if (check(row, i)) {
                        if (row == 7) print();
                        else _solve(row+1);
                    }
                    //同一行下一列进行比较
                    board[row][i] = '0';    
                }

判断当前摆放的皇后与前面已经摆好的皇后有无冲突

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:
            // 建立一个8*8棋盘
            char board[8][8];
            // 记录有多少种摆法
            int cnt;
        public:
            void solve() {
                memset(board, '0', sizeof(board));
                cnt = 0;
                _solve(0);//从第0行开始摆放
            }
        private:
        // 参数表示第row行前面都已经摆好了
            void _solve(int row) {  
                int i;
                for (i=0;i<8;i++) {
                    board[row][i] = '1';
                    // 判断当前位置是否可以摆
                    if (check(row, i)) {
                        if (row == 7) print();
                        else _solve(row+1);
                    }
                    //同一行下一列进行比较
                    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;
            }
    };
}