回溯——八皇后

回溯——八皇后

题意解析

八皇后问题（英文：Eight queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是==回溯算法==的典型案例。 问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。

解题思路

二、如何解决八皇后问题？

　　所谓递归回溯，本质上是一种枚举法。（我们更愿意称之为“有技巧的枚举”）这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后......

　　如果某一层看遍了所有格子，都无法成功摆放，则回溯到上一个皇后，让上一个皇后右移一格，再进行递归。如果八个皇后都摆放完毕且符合规则，那么就得到了其中一种正确的解法。说起来有些抽象，我们来看一看递归回溯的详细过程。

　　1.第一层递归，尝试在第一行摆放第一个皇后：

img

　　2.第二层递归，尝试在第二行摆放第二个皇后（前两格被第一个皇后封锁，只能落在第三格）：

img

　　3.第三层递归，尝试在第三行摆放第三个皇后（前四格被第一第二个皇后封锁，只能落在第五格）：

img

　　4.第四层递归，尝试在第四行摆放第四个皇后（第一格被第二个皇后封锁，只能落在第二格）：

img

　　5.第五层递归，尝试在第五行摆放第五个皇后（前三格被前面的皇后封锁，只能落在第四格）：

img

　　6.由于所有格子都“绿了”，第六行已经没办法摆放皇后，于是进行回溯，重新摆放第五个皇后到第八格。：

img

　　7.第六行仍然没有办法摆放皇后，第五行也已经尝试遍了，于是回溯到第四行，重新摆放第四个皇后到第七格。：

img

　　8.继续摆放第五个皇后，以此类推......

代码实现

#include <iostream>
using namespace std;
const int ArSize = 8;//这个数等于几，就是几皇后。
int num = 0;
void solve(bool arr[ArSize][ArSize], int row);
bool check(bool arr[ArSize][ArSize], int row, int column);
void outPut(bool arr[ArSize][ArSize]);

int main()
{
    bool chessboard[ArSize][ArSize];
    // 数组初始化
    for (auto &i : chessboard)
    {
        for (auto &j : i)
        {
            j = false;
        }
    }
    solve(chessboard, 0);
    cout << "八皇后问题共有" << num << "种解！" << endl;
    system("pause");
    return 0;
}

// 回溯法
void solve(bool arr[ArSize][ArSize], int row)
{
    for (int column = 0; column < ArSize; ++column)
    {
        arr[row][column] = true;        //在确定的某一行，遍历每一列放下棋子
        if (check(arr, row, column))    //满足条件：1.继续在下一行放下棋子；2.如果是最后一行，输出矩阵
        {
            if (row + 1 == ArSize)
            {
                outPut(arr);
            }
            else
            {
                solve(arr, row + 1);
            }
        }
        arr[row][column] = false;
    }
}
// 判断皇后的落点是否合规
bool check(bool arr[ArSize][ArSize], int row, int column)
{
    if (row == 0)
    {
        return true;//第一行不需要判断
    }
    int i, j;
    // 判断纵向是否有冲突
    for (i = 0; i < row; ++i)
    {
        if (arr[i][column])
        {
            return false;
        }
    }
    i = row - 1;
    j = column - 1;
    // 判断正斜对角线是否有冲突
    while (i >= 0 && j >= 0)
    {
        if (arr[i][j])
        {
            return false;
        }
        --i;
        --j;
    }
    i = row - 1;
    j = column + 1;
    // 判断负斜对角线是否有冲突
    while (i >= 0 && j <= ArSize - 1)
    {
        if (arr[i][j])
        {
            return false;
        }
        --i;
        ++j;
    }
    return true;
}
// 打印每种正确的解法
void outPut(bool arr[ArSize][ArSize])
{
    ++num;
    cout << "**********************" << num << "*********************" << endl;
    for (int i = 0; i < ArSize; ++i)
    {
        for (int j = 0; j < ArSize; ++j)
        {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    cout << "*********************************************" << endl;
}

参考资料

[1]https://www.cnblogs.com/smile233/p/8483729.html

[2]https://baike.baidu.com/item/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98