回溯法经典例题——python

1.七段码：练习系统

求解：思路就是组合，首先利用哈希表来存储所有字符和与它邻接的字符，其次求满足要求的组合。

代码讲解如下（各位看官可自我进行改进），另一种直接暴力的算法请参考这篇文章

#七段码#组合+回溯
Last={'a':['b','f'],'b':['a','c','g'],'c':['b','g','d'],'d':['c','e'],
'e':['d','f','g'],'f':['a','e','g'],'g':['b','c','e','f']}#哈希存储
def bfs(path,s,n):#定义回溯函数
    if len(path)==n:#结束条件
        kk=''.join(sorted(path))#对组合进行大小排序
        if kk not in AA:#是否满足条件要求
            AA.append(kk)#结果增加
        return
    for i in Last[s]:
        if i not in path:#剪枝 *** 作
            path.append(i)#添加路径
            bfs(path,i,n)#下一节点
            path.pop()#路径回溯
if __name__=='__main__':
    AA=[]
    for n in range(1,8):
        for j in 'abcdefg':
            bfs([j],j,n)#调用回溯函数
    print(len(AA))
    print(AA)

输出结果和满足要求的组合：

2.年串字号：练习系统

#年串字号#回溯+组合
import itertools
SS='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def dfs(path,n):
    if len(path)==n:#结束条件
        VAL.append(''.join(path))#结果增加
        return
    for i in SS:#单纯的组合，所以不用在剪枝 *** 作时不用增加判断条件
        path.append(i)#路劲增加
        dfs(path,n)#下一节点
        path.pop()#回溯
if __name__=='__main__':
    VAL=[]
    for i in range(1,4):
        dfs([],i)
    print(VAL.index('AZ'))
    print(VAL.index('AB'))
    print(VAL.index('LQ'))
    print(VAL[2018])

另一种解法如下：就是26一个循环周期，看2019循环了的最后一个是第几位数字（即最后一位字母）。

就是将2019拆分，只不过它的周期是26的倍数。

#年串字号#找规律
# # 个位
# a = 2019 % 26
# b = 2019 // 26
# # 十位
# c = b % 26
# # 百位
# d = b // 26
# list = '*ABCDEFGHIJKLMNOPQRSTUVWXYZ'
# print(list[d] + list[c] + list[a])

3.正整数的分解：也是组合的思想，但随着数的增大，时间复炸度较高

#整数的分解#回溯法
def Fenjie(path,SS,n):
    if sum(SS)==num:
        # print(SS)
        GG.add(tuple(SS))
        return
    if n>=len(Com_Val):
        return
    for i in range(n,len(Com_Val)):
        if i not in path:#剪枝
            path.append(i)路径添加
            SS.append(Com_Val[i])#下一节点
            Fenjie(path,SS,i+1)
            path.pop()
            SS.pop()

if __name__=='__main__':
    num=int(input())
    Com_Val=[]
    for i in range(1,num):
        Com_Val+=[i]*(num//i)#表示最多由N//i个i组成
    print(Com_Val)
    GG=set()
    for i in range(len(Com_Val)):
        Fenjie([i],[Com_Val[i]],i+1)
    print(GG)

在这里推荐一个小哥的思路：就是找它的状态和每一种转移状态。

#正整数的分解
def dfs(n,m):
    if n<=0 or m<=0:#不存在分解为0或负值的情况
        return 0
    if n==1 or m==1:#分解为最小值1时只有一种情况
        return 1
    if n==m:#当用自己本身分解自己时等于用比自己小的一个数分解自己的情况+1
        return 1+dfs(n,m-1)
    if n<m:#当分解自己的数比自己大时，因为不存在负值，所以等于用本身分解自己
        return dfs(n,n)
    if n>m:#当分解自己的数比自己小时，有两种情况，一种是包含分解数本身dfs(n-m,m)，一种是不包含分解数本身
        return dfs(n-m,m)+dfs(n,m-1)
if __name__=='__main__':
    N=int(input())
    print(dfs(N,N))

4.回路计数查看另一篇文章回路计数
5.N皇后问题：

#N皇后问题
def judge(i,j,Zuo):
    for nn in range(1,N+1):
        if (i+nn,j-nn) in Zuo or (i+nn,j+nn) in Zuo or (i-nn,j-nn) in Zuo or (i-nn,j+nn) in Zuo:
            return False
    else:
        return True
def DFS(X,Y,path):#回溯函数
    if len(path)==N:
        num=sorted(path,key=lambda x:x[0])
        if tuple(num) not in KK:#加这个选择条件的目的是为了去除重复
            print(num)
            KK.add(tuple(num))
        return
    for i in range(N):
        if len(path)!=0 and path[0][0]==1:#加这个条件是目的也是为了去除重复
            break
        for j in range(N):
            if i not in X and j not in Y and judge(i, j, path):#剪枝 *** 作
                X.append(i)#路径添加
                Y.append(j)
                path.append((i, j))
                DFS(X,Y,path)#下一节点
                X.pop()#回溯
                Y.pop()
                path.pop()
if __name__=='__main__':
    KK=set()
    N=int(input())
    DFS([],[],[])#时间复杂度为n**n
    print(len(KK))
    print(KK)