八皇后问题

皇后：国际象棋中威力最强的一颗棋子，走法是横、直、斜走均可，格数不限，不可越子

国际象棋：在8*8的方格上进行的一种快乐游戏

棋盘
八皇后问题：如何在8*8的棋盘上摆放八个皇后使其不能互相攻击

思考

看到这个问题，首先想到的就是不断进行尝试，暴力求出所有可能性。但是这样会有种情况，耗时太多。

自然的，就会想到可不可以提前判断，如果棋子已经放在了不恰当的位置，就直接舍弃之后的所有可能性

第二行的棋子落下
第二行的棋子落下时，Queen们就会互相攻击，所以就不必继续放置接下来的
种情况 来自维基的动图

代码

声明部分

#include <iostream>
using namespace std;

const int N = 8;  //N值代表几皇后问题
int chessboard[N][N] = { 0 };   //定义棋盘大小
int solve_num = 0; //解的数目

我们采用二维数组，可以更加直观的表达棋盘的情况
N值可根据情况任意改变，如N=4即为四皇后问题

判断部分

bool check(int row, int col)
{
    if (row == 0) return true;
    for (int i = 0; i != row; ++i){
        if (chessboard[i][col] == 1) 
            return false;   //每列(col)只能有一个棋子
    }
    for (int j = 0; j != col; ++j){
        if (chessboard[row][j] == 1) 
            return false;  //每行(row)只能有一个棋子
    }

/*把i和j的值分别置为比当前棋子位置的值少一，即为左上角一格，
i >= 0 && j >= 0;控制i和j在棋盘范围内，
--i, --j；向左上角移动
*/

    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j){
        if (chessboard[i][j] == 1) 
            return false;  //判断左上角是否有棋子
    }

/*i的值为当前棋子的行值减一，j的值为当前棋子的列值加一，即为右上角一格，
i != N && j != N; 控制i和j在棋盘范围内，
--i, ++j；向右上角移动
*/
    for (int i = row - 1, j = col + 1; i >= 0 && j != N; --i, ++j){
        if (chessboard[i][j] == 1) 
            return false; //判断右上角是否有棋子
    }
    //如果行、列和对角线都没有其他棋子，则返回true
    return true;
}

输出部分

void print()
{
    int row, col;         //行，列
    ++solve_num;    //每次执行该输出函数，全局变量solve_num就会加一，代表解的数目加一
    cout << "Solution " << solve_num << ":" << endl;
    for (row = 0; row != N; ++row) {
        for (col = 0; col != N; ++col) {
            cout << chessboard[row][col] << ends;
        }
        cout << endl;
    }
}

递归函数实现回溯法

void solve(int row)
{
    int col; //列
    for (col = 0; col != N; ++col){
        chessboard[row][col] = 1; //在第row行的其中一列放置皇后
        if (check(row, col) == true){ //检查放置皇后位置是否合法
            if (row == N - 1){  //检查合法后，如该行已经是棋盘最后一行
                print();        //打印出该解法
            }
            else{                //如果不是最后一行
                solve(row + 1);//就继续判断下一行的皇后要放在哪个位置
            }
        }

        chessboard[row][col] = 0;//如检查不合法，就把放置的皇后撤走(即1变0)
    }
}

递归时不要过于纠结每步是如何实现的，那是程序要完成的工作，

我们只要坚信，递归结果是正确的

主函数

int main()
{
    solve(0); //传入第 0行
    return 0;
}

运行结果

四皇后：

四皇后

十四皇后：

十四皇后

个人主页

http://spaceman.site/

欢迎访问