1-八皇后

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;
            }
    };
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。