回溯法：八皇后问题

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

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

这个问题简化描述就是：在8x8的棋盘上放8颗子，要求它们【不在同一行】【不在同一列】【不在同一斜线】上。  
我们可以定义一个数组position\[8\]，positon\[i\]=j代表第i行摆在第j列。所以我们的约束条件可以进行如下表示：  
1. 不在同一列：position\[i\] ≠ position\[j\]  
2. 不在同一主对角线：position\[i\] - i ≠ position\[j\] - j  
3. 不在同一副对角线：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种摆法：  
![运行结果][20150517122212430]

--------------------

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

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

[20150517122212430]: /images/20220805/f7d3d9b5973f43a981dcf1e8bf2121d1.png