In The End

个人博客

0%

回溯法：n皇后问题（C++与Python3）

发表于 更新于 分类于

hello，我又更新博客了。今天来写一个非常著名的算法——回溯法，而且这次加上了Python的代码实现。

那么首先来介绍一下今天的主角——回溯法。先借用刘汝佳大佬的话：回溯法是初学者学习暴力法的第一个障碍，学习时间短则数天，长则数月甚至一年以上。听起来有点吓人，对于回溯法，我个人的理解是DFS（深度优先搜索）的一种转化，先对所求目标深入查找，成功则输出，失败则将深入查找过程中修改的值改回来然后换一条路继续搜。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

我们先从八皇后问题开始看起：八皇后问题，是一个古老而著名的问题，是[回溯算法]的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 [高斯]认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

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

八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。

艾兹格·迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力。没错就是我们最短路径dijkstra算法的创造者（有兴趣的童鞋可以去了解一下这个牛人和他创造的算法）


上图的皇后排布就是一种解法 我们举一反三，如何解决N皇后的问题呢，我们的思路如下：本算法的思路是按行来规定皇后位置，第一行放置一个皇后，第二行放置一个皇后， 第N行也放置一个皇后… 这样， 可以保证每行都有一个皇后，那么各行的皇后应该放置在那一列呢， 算法通过循环来完成，在循环的过程中， 一旦找到一个合适的列，则该行的皇后位置确定，则继续进行下一行的皇后的位置的确定。由于每一行确定皇后位置的方式相似，所以可以使用递归法。一旦最后 一行的皇后位置确定，则可以得到一组解。找到一组解之后， 之前确定皇后应该放置在哪一列的循环其实才进行了一轮循环的， 算法通过该循环遍历所有的列，以此确定每一行所有可能的列的位置。在从一轮循环进入下一轮循环之前，算法需要清除在上一轮被标记为不可放置皇后的标记，也就是回溯。因为进入下一轮循环之后，同一行的皇后的列的位置会发生了变化，之前被标记为不可放置皇后的列和正反对角线位置都已经失效
下面给出N皇后问题代码实现:

C++版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstring>
using namespace std;

int tot;
int vis[3][100];//使用二维数组，分别枚举列和两个对角线

void queen(int n,int *A,int cur){
    if(cur==n)
        tot++;
    else{
        for(int i=0;i<n;i++){
            if(!vis[0][i]&&!vis[1][i+cur]&&!vis[2][cur-i+n]){
                A[cur]=i;
                vis[0][i]=vis[1][i+cur]=vis[2][cur-i+n]=1;
                queen(n,A,cur+1);
                vis[0][i]=vis[1][i+cur]=vis[2][cur-i+n]=0;
            }
        }
    }
}

int main(){
    int n;
    while(cin>>n) {
        int *a = new int[n+10];
        memset(vis,0, sizeof(vis));
        tot=0;
        queen(n,a,0);
        cout << tot << endl;
    }
    return 0;
}

python3版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#这种是常规版的，使用一位数组回溯
def queen(c,cur):
    if(cur==n):
        global tot
        tot+=1
    else:
        for i in range(0,n):
            ok=1
            c[cur]=i;
            for j in range(0,cur):
                if(c[cur]==c[j] or cur-c[cur]==j-c[j] or cur+c[cur]==j+c[j]):
                    ok=0
                    break
            if(ok):
                queen(c,cur+1)
#这个跟上面的C++版本相同，使用了二维数组存储
def queen2(c,cur):
    global tot
    global vis
    if(cur==n):
        tot+=1
    else:
        for i in range(n):
            if(vis[0][i] == 0 and vis[1][cur+i] == 0 and vis[2][cur+n-i] == 0):
                c[cur]=i
                vis[0][i]=vis[1][cur+i]=vis[2][cur+n-i]=1
                queen2(c,cur+1)
                vis[0][i]=vis[1][cur+i]=vis[2][cur+n-i]=0
#主函数
if __name__=='__main__':
    while True:
        try:
            n=int(input());
            tot=0
            vis=[[0 for col in range(n+10)] for row in range(3)]
            print(vis)
            c=[0]*n
            queen2(c,0)
            print(tot)
        except EOFError:
            break

OK，今天的回溯法讲完了，当然这只是回溯法的九牛一毛而已，接下来会给大家带来更多回溯法的应用问题