本文共 5457 字，大约阅读时间需要 18 分钟。

是回溯递归思想的展现。

回溯法和枚举法的区别

回溯法与穷举法有某些联系，它们都是基于试探的。

穷举法要将一个解的各个部分全部生成后，才检查是否满足条件，若不满足，则直接放弃该完整解，然后再尝试另一个可能的完整解，它并没有沿着一个可能的完整解的各个部分逐步回退生成解的过程。 而对于回溯法，一个解的各个部分是逐步生成的，当发现当前生成的某部分不满足约束条件时，就放弃该步所做的工作，退到上一步进行新的尝试，而不是放弃整个解重来。

实现1：百度百科八皇后问题里面的python实现

def queen(A, cur=0):    global num    if cur == len(A):        print(A)  # 打印解，每个位置对应的列        num += 1        return 0    for col in range(len(A)):        A[cur], flag = col, True        for row in range(cur):            # 如果检测出前面的行和当前行是同列的，或者在当前点的等腰直角三角形上            if A[row] == col or abs(col - A[row]) == cur - row:                flag = False                break        if flag:  # 如果当前点合适的话那就下一个点，如果当前点不合适的话那就当前点往右再走一步            queen(A, cur+1)num = 0queen([None]*8)print(num)

暴力解法盲目的枚举算法：通过8重循环模拟搜索空间中的8个状态，从中找出满足约束条件的“答案状态”。下面的算法总共需要8^8=2^24

优点：程序思想比较简单

缺点：问题转化为“从64个格子中选一个子集”，使得“子集中恰好有8个格子，且任意选出两个格子都不在同一行，同一列或者同意对角线上”。这恰好是子集枚举问题。然而，64个格子的子集有2^64个，太大了，则并不是一个很好的模型。

def queens():    a=[None]*8    count=0    for i0 in range(8):        a[0]=i0        for i1 in range(8):            a[1]=i1            for i2 in range(8):                a[2]=i2                for i3 in range(8):                    a[3]=i3                    for i4 in range(8):                        a[4]=i4                        for i5 in range(8):                            a[5]=i5                            for i6 in range(8):                                a[6]=i6                                for i7 in range(8):                                    a[7]=i7                                    if check(a):                                        count +=1                                        # print(' '.join(map(str,a)))    return countdef check(a):    n=len(a)    for i in range(1,n):        for j in range(i):            if a[i]==a[j] or abs(a[i]-a[j])==i-j:                return False    return True                    count=queens()print(count)

考虑到其中的限制条件，不能同行同列，那么第一行8个位置，第二行7个位置，第三行6个位置，这样算法总共只需要8！=40320

枚举的次数不会超过这个值。当前判断如果走不通就掉头，缺点也是一样的，对于n未知的情况或者n非常大的情况，写法是不好的（需要n个for循环）

def queens():    a=[None]*8    count=0    for i0 in range(8):        a[0]=i0        for i1 in range(8):            a[1]=i1            if check(a,1):                continue            for i2 in range(8):                a[2]=i2                if check(a,2):                    continue                for i3 in range(8):                    a[3]=i3                    if check(a,3):                        continue                    for i4 in range(8):                        a[4]=i4                        if check(a,4):                            continue                        for i5 in range(8):                            a[5]=i5                            if check(a,5):                                continue                            for i6 in range(8):                                a[6]=i6                                if check(a,6):                                    continue                                for i7 in range(8):                                    a[7]=i7                                    if check(a,7):                                        continue                                    else:                                        count +=1                                        # print(' '.join(map(str,a)))    return countdef check(a,n):    for i in range(n):        if a[i]==a[n] or abs(a[n]-a[i])==n-i:                return False    return True                    count=queens()print(count)

上述，它只针对八皇后问题，解决任意的n皇后问题还要修改程序结构。如果要解决n皇后的问题，就需要将n作为参数传递给函数，函数需要重写来实现回溯（不能采用级联的for循环，n不确定）；从另一方面，程序中出现了大量的for循环，而且for中的函数结构很相似，自然想到的是递归迭代回溯。这就是回溯比较常用的两种实现方法：非递归回溯和递归回溯。

递归回溯法：

def queens(A,k=0):    global count    if k==len(A):        print(A)        count +=1        return 0    for i in range(len(A)):        A[k]=i        if not check(A,k):            continue        else:            queens(A,k+1)def check(a,n):    for i in range(n):        if a[i]==a[n] or abs(a[n]-a[i])==n-i:                return False    return True                    count =0queens([None]*8,k=0)print(count)

非递归方法：比较复杂，暂时还没有转化成python，下面只给出C++语言的实现

void backdate (int n){      int count = 0;    int a[100];    int k = 1;    a[1]=0;       while(k>0)    {        a[k]=a[k]+1;//对应for循环的1~n        while((a[k]<=n)&&(!check_2(a,k)))//搜索第k个皇后位置        {            a[k]=a[k]+1;        }                  if(a[k]<=n)//找到了合理的位置        {            if(k==n )            {//找到一组解                for(int i=1;i<=8;i++)                  {                    cout<

下面的一道题

描述

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。

给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 <= b <= 92)

输出

输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。

样例输入

2192

样例输出

1586372484136275

# 给n皇后问题的所有解进行排序，按从小到大的顺序：例如，其中三组解[6 4 2 0 5 7 1 3],[6 1 5 2 0 3 7 4]，[7 2 0 5 1 4 6 3]；# 排序后是[6 1 5 2 0 3 7 4]，[6 4 2 0 5 7 1 3],[7 2 0 5 1 4 6 3]# 从上面打印可以看出，打印的顺序就是从小打到的顺序。def queens(A,k=0):    global count,seek    if k==len(A):        # print(A)        count +=1        if count==seek:            print(A)        return 0    for i in range(len(A)):        A[k]=i        if check(A,k):            queens(A,k+1)           def check(a,n):    for i in range(n):        if a[i]==a[n] or abs(a[n]-a[i])==n-i:                return False    return True                    count,seek =0,1queens([None]*8,0)print(count)

 

 

 

 

 

 

 

 

 

 

 

转载地址：http://ecwbf.baihongyu.com/