回溯法：八皇后问题-蒲公英云

回溯法：八皇后问题

蔚落 2022-08-08 12:45 289阅读 0赞

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

这个问题简化描述就是：在8x8的棋盘上放8颗子，要求它们【不在同一行】【不在同一列】【不在同一斜线】上。
我们可以定义一个数组position[8]，positon[i]=j代表第i行摆在第j列。所以我们的约束条件可以进行如下表示：

不在同一列：position[i] ≠ position[j]
不在同一主对角线：position[i] - i ≠ position[j] - j
不在同一副对角线：position[i] + i ≠ position[j] + j
其中2和3可以合并成abs(i - j) ≠ abs(position[i] - position[j])

求解思路：
首先从第一个皇后开始，从第一行确定第一个皇后位置，然后再在第二行搜索第二个皇后位置……没前进一步检查是否满足约束条件，不满足的时候回溯到上一个皇后位置，尝试该行的其他列是否满足条件，直到找到问题的解。

C++参考代码：

#include <iostream>
using namespace std;
const int N = 8;//皇后的个数
int positon[N];//存放皇后的位置
int count = 0;//记录有多少种摆法
/*判断第row行放置的位置是否满足要求*/
bool valid(int row)
{
    for (int i = 0; i <  row; ++i)
    {
        // 如果和前面放好位置的不在同一列，也不在对角线上，则返回true，否则返回false
        if (positon[i] == positon[row] || abs(positon[i] - positon[row]) == abs(i - row))
        return false;
    }
    return true;
}
/*输出摆放结果*/
void print()
{
    cout << "这是第" << ++count << "种摆法：" << '\n';
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (positon[i] == j)
                cout << "⊙ ";
            else
                cout << "× ";
        }
        cout << '\n';
    }
    cout << endl;
}
/*回溯法搜索摆放位置*/
void trail(int row = 0)
{
    // 如果摆完完N行，则输出结果
    if (N == row)
    {
        print();
        return;
    }
    for (int column = 0; column < N; ++column)
    {
        positon[row] = column;// 放置在第row行第column列
        // 如果满足条件，则进行下一行
        if (valid(row)) trail(row + 1);
        // 如果不满足条件，则进行下一次循环，即回溯回去在第row行重新寻找摆放的位置
    }
}
int main()
{
    trail();
    return 0;
}

总共有92种摆法：
运行结果

下面官方的说一下回溯法（摘自百度百科）。
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

基本思想：
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束