回溯法

回溯法简述

回溯法是暴力法的升级版，我们可以将其解决问题的过程想象成一颗树，属于树型问题。

从根节点R开始，一步一步向下走，而每一步都会有多个（有限个）选择，对应多个子节点（A, B, C…）。若当前节点A匹配成功，则进入该节点的子节点（A-1, A-2, A-3…）继续匹配；若当前节点A匹配失败，则回到其父节点，继续匹配其他未曾匹配过的A的兄弟节点（B, C…），此过程称为回溯。

整个过程可以通过递归实现（深度优先遍历），也可以用栈实现。

算法题案例

矩阵中的路径

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路

python

class Solution:
    def judge(self, matrix, path, r, c, length):
        idx = self.cols * r + c # 由于matrix为字符串形式，需手动根据r和c获取一维索引号
        if(r < 0 or r >= self.rows or       # 越界
           c < 0 or c >= self.cols or       # 越界
           matrix[idx] != path[length] or   # 当前元素不匹配
           self.visited[r][c] == 1):        # 当前元素已访问
            return False
        length += 1
        if(len(path) == length): # 已找到一条路径
            return True
        self.visited[r][c] = 1 # 当前元素标记为已访问
        if(self.judge(matrix, path, r-1, c, length) or # 上侧
           self.judge(matrix, path, r+1, c, length) or # 下侧
           self.judge(matrix, path, r, c-1, length) or # 左侧
           self.judge(matrix, path, r, c+1, length)):  # 右侧
            return True
        self.visited[r][c] = 0 # 回溯回来，将当前元素标记为未访问

    def hasPath(self, matrix, rows, cols, path): # main
        self.rows = rows
        self.cols = cols
        self.visited = [[0 for _ in range(cols)] for _ in range(rows)] # 记录对应元素是否已访问
        
        # 对matrix中每一个元素进行遍历判断
        for r in range(rows):
            for c in range(cols):
                if(self.judge(matrix, path, r, c, 0)): # 只要找到一条路径，直接返回True
                    return True
        return False

运行结果

python

solu = Solution()
print(solu.hasPath("ABCESFCSADEE",3,4,"ABFDEESE"))

>>> True

扩展

• 同时记录path所经过的路径坐标(self.path相关部分的代码)

python

class Solution:    
    def judge(self, matrix, path, r, c, length):
        idx = self.cols * r + c # 由于matrix为字符串形式，需手动根据r和c获取一维索引号
        if(r < 0 or r >= self.rows or       # 越界
           c < 0 or c >= self.cols or       # 越界
           matrix[idx] != path[length] or   # 当前元素不匹配
           self.visited[r][c] == 1):        # 当前元素已访问
            return False
        length += 1
        if(len(path) == length): # 已找到一条路径
            self.path.append((r, c)) # 将最后的坐标入栈
            return True
        self.path.append((r, c)) # 当前元素匹配，将其坐标入栈
        self.visited[r][c] = 1 # 当前元素标记为已访问
        if(self.judge(matrix, path, r-1, c, length) or # 上侧
           self.judge(matrix, path, r+1, c, length) or # 下侧
           self.judge(matrix, path, r, c-1, length) or # 左侧
           self.judge(matrix, path, r, c+1, length)):  # 右侧
            return True
        self.visited[r][c] = 0 # 回溯回来，将当前元素标记为未访问
        self.path.pop() # 回溯回来，将当前元素坐标出栈

    def hasPath(self, matrix, rows, cols, path): # main
        # write code here
        self.rows = rows
        self.cols = cols
        self.visited = [[0 for _ in range(cols)] for _ in range(rows)] # 记录对应元素是否已访问
        self.path = [] # 用来记录路径的坐标
        
        # 对matrix中每一个元素进行遍历判断
        for r in range(rows):
            for c in range(cols):
                if(self.judge(matrix, path, r, c, 0)): # 只要找到一条路径，直接返回True
                    return True
        return False

• 运行结果

python

solu = Solution()
print(solu.hasPath("ABCESFCSADEE",3,4,"ABFDEESE"))
print(solu.path)

>>> True
>>> [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (1, 3), (0, 3)]

机器人的运动范围

题目来源：剑指Offer
题目链接：牛客网-剑指Offer
题目描述：

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

解题思路

python

class Solution:
    def count(self, r, c): # 计算横纵坐标各数位之和
        s = 0
        while(r):
            s += r % 10
            r //= 10
        while(c):
            s += c % 10
            c //= 10
        return s

    def judge(self, r, c):
        if(r < 0 or r >= self.rows or # 越界
           c < 0 or c >= self.cols or # 越界
           self.visited[r][c] == 1):  # 已访问
            return
        if(self.count(r, c) > self.threshold): # 坐标数位之和超过阈值则stop
            return
        self.length += 1 # 机器人可访问的格子数+1
        self.visited[r][c] = 1 # 标记当前位置已访问
        self.judge(r-1, c) # 上侧
        self.judge(r+1, c) # 下侧
        self.judge(r, c-1) # 左侧
        self.judge(r, c+1) # 右侧

    def movingCount(self, threshold, rows, cols): # main
        self.threshold = threshold
        self.rows = rows
        self.cols = cols
        self.length = 0 # 记录机器人可访问的格子数，初始化为0
        self.visited = [[0 for _ in range(cols)] for _ in range(rows)] # 记录对应位置是否已访问

        self.judge(0, 0) # 从(0, 0)位置开始遍历
        return self.length

注意：这道题没有进行 ‘self.visited[r][c] = 0’ 取消访问标记的操作，因为这道题问的是最多能到达的格子数，若改成能通过的最长路径，则需要取消标记。

运行结果

python

solu = Solution()
print(solu.movingCount(5, 10, 10))
print(solu.movingCount(10, 1, 100))

>>> 21
>>> 29

电话号码的字母组合

题目来源：Leetcode
题目链接：Leetcode-17
题目描述：

给定一个仅包含数字 2 - 9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

解题思路

深度优先遍历即可

python

class Solution:
    def __init__(self):
        self.dict = dict({'0':'',
                          '1':'',
                          '2':'abc',
                          '3':'def',
                          '4':'ghi',
                          '5':'jkl',
                          '6':'mno',
                          '7':'pqrs',
                          '8':'tuv',
                          '9':'wxyz'})
        self.result = []
    
    def backtrack(self, digits, idx, curr):
        if(idx == len(digits)):
            self.result.append(curr) # 当前字符串达到长度要求时，返回
            return
        for c in self.dict[digits[idx]]:
            self.backtrack(digits, idx + 1, curr + c) # 递归下一个数字对应的字母
    
    def letterCombinations(self, digits): # main
        if(digits == ''):
            return []
        self.backtrack(digits, 0, '')
        return self.result

运行结果

python

solu = Solution()
print(solu.letterCombinations("23"))

>>> ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

解数独

题目来源：Leetcode
题目链接：Leetcode-37
题目描述：

编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
1、数字 1-9 在每一行只能出现一次。
2、数字 1-9 在每一列只能出现一次。
3、数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

一个数独。

答案被标成红色。

解题思路

• 按照从左到右、从上到下的顺序遍历所有位置
• 从1~9选择合适的数字依次填入
  • 若当前无合适的数字，则回溯
  • 若已到达最后位置，则数独已解决

python

class Solution(object):
    def placeNum(self, r, c, num): # 更新Flags
        self.rowFlag[r][num] = 1
        self.colFlag[c][num] = 1
        self.boxFlag[r//3*3 + c//3][num] = 1

    def removeNum(self, r, c, num): # 移除Flags
        self.rowFlag[r][num] = 0
        self.colFlag[c][num] = 0
        self.boxFlag[r//3*3 + c//3][num] = 0

    def judge(self, r, c, num): # 判断当前位置能否填入数字num
        if(not self.rowFlag[r][num] and
           not self.colFlag[c][num] and
           not self.boxFlag[r//3*3 + c//3][num]):
            return True
        else:
            return False

    def placeNext(self, r, c): # 判断数独是否已解决，并填入下一个数字
        if(r == 8 and c == 8): # 若当前位置已有数字且为最后一位
            self.solved = True # 数独已解决
            return
        # 总体按照从左到右、从上到下的顺序进行递归
        if(c == 8): # 若当前为最右侧的位置，则从下一行头部继续递归
            self.backtrack(r+1, 0)
        else: # 否则递归计算右侧一格
            self.backtrack(r, c+1)

    def backtrack(self, r, c):
        if(r >= 9 or c >= 9):
            return
        if(self.board[r][c] != '.'): # 当前位置已有数字
            self.placeNext(r, c) # 填入下一个数字
        else:
            for i in range(1, 10): # 从1到9进行遍历
                if(self.judge(r, c, i)): # 判断当前位置是否能填该数字
                    self.board[r][c] = str(i) # 填入数字
                    self.placeNum(r, c, i) # 更新Flags

                    self.placeNext(r, c) # 填入下一个数字

                    if(not self.solved): # 若数独还未解决，则回溯时需清除填入的信息；否则保留填入的信息
                        self.board[r][c] = '.' # 移除数字
                        self.removeNum(r, c, i) # 移除Flags

    def solveSudoku(self, board): # main
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        self.board = board
        self.rowFlag = [[0 for _ in range(10)] for _ in range(9)] # 行标识，每一行1~9
        self.colFlag = [[0 for _ in range(10)] for _ in range(9)] # 列标识，每一列1~9
        self.boxFlag = [[0 for _ in range(10)] for _ in range(9)] # 块标识，3x3九宫格1~9
        self.solved = False # 数独是/否解决 标识位

        # 初始化Flags
        for r in range(9):
            for c in range(9):
                if(board[r][c] != '.'):
                    num = int(board[r][c])
                    self.placeNum(r, c, num)
        # 从头部开始递归
        self.backtrack(0, 0)

运行结果

python

from pprint import pprint
solu = Solution()
solu.solveSudoku([['5', '3', '.', '.', '7', '.', '.', '.', '.'],
                  ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
                  ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
                  ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
                  ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
                  ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
                  ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
                  ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
                  ['.', '.', '.', '.', '8', '.', '.', '7', '9']])
pprint(solu.board)

>>> [['5', '3', '4', '6', '7', '8', '9', '1', '2'],
     ['6', '7', '2', '1', '9', '5', '3', '4', '8'],
     ['1', '9', '8', '3', '4', '2', '5', '6', '7'],
     ['8', '5', '9', '7', '6', '1', '4', '2', '3'],
     ['4', '2', '6', '8', '5', '3', '7', '9', '1'],
     ['7', '1', '3', '9', '2', '4', '8', '5', '6'],
     ['9', '6', '1', '5', '3', '7', '2', '8', '4'],
     ['2', '8', '7', '4', '1', '9', '6', '3', '5'],
     ['3', '4', '5', '2', '8', '6', '1', '7', '9']]

N皇后

题目来源：Leetcode
题目链接：Leetcode-51
题目描述：

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

解题思路

N皇后问题实际上就是在NxN的数组中，对每一行找到一个位置，使得最终N个皇后不同行、不同列、不处于同一个主副对角线，我们最终要得到的结果实际上是一个list，其中第 i 个元素值 j 代表第 i 行的皇后处于第 j 列。
因此，我们只需要遍历每一行的N个值，遇到冲突时回溯即可。

对于所有的主对角线有 行号 + 列号 = 常数，对于所有的副对角线有 行号 - 列号 = 常数。

python

class Solution(object):
    def backtrack(self, r, c):
        if(r >= self.n or c >= self.n or # 越界
           self.mainDiagFlag[r-c] or     # 主对角线冲突
           self.counterDiagFlag[r+c] or  # 副对角线冲突
           self.rowFlag[r] or            # 行冲突
           self.colFlag[c]):             # 列冲突
            return
        self.mainDiagFlag[r-c], self.counterDiagFlag[r+c] = 1, 1
        self.rowFlag[r], self.colFlag[c] = 1, 1
        self.seq.append(c)
        if(len(self.seq) == self.n): # 若当前序列已完成，则将其入栈self.result
            self.result.append(list(self.seq)) # 若不加list()，会导致入栈内容为空
        for i in range(self.n): # 对下一行的每个位置进行遍历递归
            self.backtrack(r+1, i)
        self.mainDiagFlag[r-c], self.counterDiagFlag[r+c] = 0, 0
        self.rowFlag[r], self.colFlag[c] = 0, 0
        self.seq.pop()

    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        if(n <= 0):
            return []
        self.n = n
        self.mainDiagFlag = [0 for _ in range(2 * n - 1)]       # 主对角线标识
        self.counterDiagFlag = [0 for _ in range(2 * n - 1)]    # 副对角线标识
        self.rowFlag = [0 for _ in range(n)]                    # 行标识
        self.colFlag = [0 for _ in range(n)]                    # 列标识
        self.seq = [] # 单个结果序列，seq[i]=j 代表第i行第j列放上皇后
        self.result = [] # 最终结果

        for c in range(n): # 对第1行的每个位置进行遍历递归
            self.backtrack(0, c)
        return [['.'*c + 'Q' + '.'*(n-c-1) for c in seq] for seq in self.result] # 返回题目要求的输出格式

运行结果

python

solu = Solution()
print(solu.solveNQueens(4))

>>> [['.Q..', 
      '...Q', 
      'Q...', 
      '..Q.'],

     ['..Q.', 
      'Q...', 
      '...Q', 
      '.Q..']]

优化

注意一个细节：一行只可能有一个皇后，一列也只可能有一个皇后。
这意味着没有必要考虑棋盘上所有的方格，只需要按行或列循环即可，这样也能省掉rowFlag和colFlag这两个标识，降低复杂度。

python

class Solution(object):
    def backtrack(self, r):
        for c in range(self.n):
            if(c in self.seq or             # 列已存在序列中
               self.mainDiagFlag[r-c] or    # 主对角线冲突
               self.counterDiagFlag[r+c]):  # 副对角线冲突
                continue
            self.mainDiagFlag[r-c], self.counterDiagFlag[r+c] = 1, 1
            self.seq.append(c)
            if(len(self.seq) == self.n): # 若当前序列已完成，则将其入栈self.result
                self.result.append(list(self.seq)) # 若不加list()，会导致入栈内容为空
            self.backtrack(r+1) # 递归下一行
            self.mainDiagFlag[r-c], self.counterDiagFlag[r+c] = 0, 0
            self.seq.pop()

    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        if(n <= 0):
            return []
        self.n = n
        self.mainDiagFlag = [0 for _ in range(2 * n - 1)]       # 主对角线标识
        self.counterDiagFlag = [0 for _ in range(2 * n - 1)]    # 副对角线标识
        self.seq = [] # 单个结果序列，seq[i]=j 代表第i行第j列放上皇后
        self.result = [] # 最终结果

        self.backtrack(0) # 从第1行开始遍历
        return [['.'*c + 'Q' + '.'*(n-c-1) for c in seq] for seq in self.result] # 返回题目要求的输出格式