回溯算法学习（N皇后问题）(python)

回溯算法学习（N皇后问题）(python)

最近学习了一下回溯算法，花了好长时间解决N皇后问题，因此在这里我进行记录一下。

回溯算法：实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选搜索优法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

框架：

result = []
def backtrack(路径，选择列表):
    if 满足条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径，选择列表)
        撤销选择

这里利用递归进行遍历，相当于遍历决策树，先是做选择然后递归进入该路径并继续前进，而最后的撤销选择则是为了回到上一个节点，这样才能找到所有路径。

leetcode第五十一题

我个人目前用的是python解答的，不过目前解决的时间效率不是多好，这里仅仅用于记录

import copy

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        self.N = n
        self.list_F = []
        self.listF = []
        self.list = self.board(n)
        self.backtrack(self.list,0)
        return self.listF
        
            

    def board(self,n): #初始化二维数组
        list0 = [0 for i in range(n)]
        for i in range(n):
                list0[i]='.'*n
        # print(list0)
        return list0
    
    def backtrack(self,list_0,n):
        if n == len(list_0):
            self.list_F.append(copy.deepcopy(list_0))
            return
            
         
        for i in range(len(list_0)):
            if not self.isValid(list_0,n,i):
                continue
         
            # print(list_0)
            list_0 = self.create_list_forward(list_0,n,i)
            
            self.backtrack(list_0,n+1)
            # self.list_1 = list_0
            list_0 =self.create_list_back(list_0,n,i)
        
    # def print(self):
        # print(self.listF)
       
        
    def create_list_forward(self,list0,n,i): #建立前进的二维数组
        for j in range(len(list0)):
            if j == n :
                list0[j] = "."*i+"Q"+"."*(self.N-i-1)
                # print(list0)
                return list0
    
    def create_list_back(self,list0,n,i): #建立后撤的二维数组
        for j in range(len(list0)):
            if j == n :
                list0[j] = "."*i+"."+"."*(self.N-i-1)
                return list0
                
    def isValid(self,list0,n,i): #检测是否可以放置皇后
        n1 =n2=n3= n
        i1=i2=i3=i
       
        #检查当前列
        for j in range(len(list0)):
            str = list0[j]
           
            if str[i]=='Q':
                return False
        #检查左上方是否有皇后冲突
        for j in range(len(list0)):
            str = list0[n2-1]
            if i2-1>=0:
                if str[i2-1]=='Q':
                    return False
            n2-=1
            i2-=1
        #检测右上方是否有皇后存在
        for j in range(len(list0)):
            if n3-1>=0:
                str = list0[n3-1]
                if i3+1 < self.N:
                    if str[i3+1]=='Q':
                        return False
            i3 = 1+i3
            n3 = n3-1
        return True
    
N = Solution()
N.solveNQueens(8)
print(N.list_F)

在写如上代码遇到一个问题，就是最后输出的全部都是'.'，经过研究才注意到原来python的列表变量同名但还是指向同一个地址，因此在递归过程的返回阶段全部又回到列表最初的样子。解决方法就是利用python的深拷贝copy.deepcopy()创建一个新的列表变量存储路径。