回溯法

习题预习

1. N皇后问题 - 在一个N × N的棋盘上放置N个皇后，使得它们不能相互攻击（即：不同行，不同列和不同对角线上不能有两个皇后）。
2. 0/1背包问题 - 在有限的容量下，给出一个物品列表和它们的重量和价值，找出一个最佳方案，使得总重量不超过容量限制，而总价值最大化。
3. 字符串排列 - 给定一个字符串，返回它的所有可能的排列集合。
4. 图形着色问题 - 在一个图形中，着色每个点，使得相邻的两个点都有不同的颜色，最少使用多少种颜色。
5. 八皇后问题 - 在一个8×8的棋盘上放置8个皇后，使得它们不能相互攻击。

说明知识

背朝追踪是解决问题的一种演算法，其中通过在解决方案的过程中回溯并反悔，以避免访问无用的状态和降低演算法的复杂性。这个演算法通常在求解组合问题（如最短路径、旅行商问题、数独）和搜索问题（如填字、八皇后）时使用。

在背朝追踪中，我们开始寻找问题的解决方案，并假定解决方案是正确的。如果发现某个部分无法通过限制条件，则回溯到先前考虑的状态并尝试其他解决方案。在这个过程中，我们保留了先前的计算和结果，以节省计算成本。

举一个背朝追踪演算法的例子，考虑以下问题：从一个起点开始，找到一条到达终点的最短路径。我们可以使用深度优先搜索来找到路径，并通过回溯来避免重复搜索相同的状态。以下是一个简单的背向搜索算法，在网格上搜索从起点到终点的最短路径：

def backtrack(start, end, grid, visited):
    # Base case: we have reached the end
    if start == end:
        return [end]
    
    # Check if we already visited this state
    if start in visited:
        return []
    
    visited.add(start)
    
    # Try moving in all directions
    rows, cols = len(grid), len(grid[0])
    x, y = start
    candidates = []
    
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny]:
            candidates.append((nx, ny))
    
    # Try to backtrack using each candidate
    for next_pos in candidates:
        path = backtrack(next_pos, end, grid, visited)
        if path:
            return [start] + path
    
    # No valid path found, so backtrack
    return []

使用背向搜索算法，我们可以以线性时间和空间复杂度找到从一个起点到另一个终点的最短路径。

条列重点

1. 确定问题的解空间：确定问题的可行解空间。

2. 确定解的表示：将解表示成某种数据结构（例如：数组、集合等）。

3. 确定约束条件：确定可行解的限制条件。

4. 确定搜索路径：摊开搜索树，决定搜索路径。

5. 确定搜索顺序：通常按照某种顺序进行搜索，例如，深度优先、广度优先、最小冲突等。

6. 递归搜索：根据搜索路径和搜索顺序进行递归搜索，直到找到可行解或者搜索完整个解空间。

7. 回溯：当发现不符合约束条件或无法执行下去时，则回溯到上一个选择点且检查下一个选择。

知识测验

1. 全排列问题（Permutations Problem）
   给定数字集合，找到所有可能的排列。
   答案：https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

2. 组合总数问题（Combination Sum Problem）
   给定一组数字集合和一个目标数字，找到集合中所有相加等于目标数字的组合。
   答案：https://leetcode.com/problems/combination-sum/

3. 单词搜索问题（Word Search Problem）
   给定一个矩阵和一个单词，找到该单词是否存在于矩阵中。单词可以是垂直或水平排列的。
   答案：https://leetcode.com/problems/word-search/

4. n皇后问题（N-Queens Problem）
   给定棋盘大小n和皇后的数量，找到皇后可以互相攻击的所有可能排列位置。
   答案：https://leetcode.com/problems/n-queens/

5. 数独问题（Sudoku Problem）
   给定一个9x9的空数独游戏板，找到解决方案。
   答案：https://leetcode.com/problems/sudoku-solver/