回溯算法举例

回溯算法概述

回溯算法是一种系统地搜索问题解空间的方法，通过逐步构建解决方案，并在发现当前解不满足条件时回溯到上一步，从而尝试其他可能的解。回溯算法广泛应用于组合优化问题、约束满足问题等。

• N皇后问题：将N个皇后放置在N×N的棋盘上，使得它们互不攻击。
• 数独：填充数独网格，使每行、每列和每个3×3子网格都包含数字1到9且不重复。
• 全排列：生成一个集合的所有排列。
• 子集生成：生成一个集合的所有子集。
  回溯算法通过系统地构建解决方案并在必要时回溯，是解决组合优化问题和约束满足问题的强大工具。理解和应用回溯算法可以有效地解决许多实际问题。以下是几个经典的回溯算法示例：

1. N皇后问题（N-Queens Problem）

N皇后问题是指将N个皇后放置在N×N的棋盘上，使得任意两个皇后都不能在同一行、同一列或同一斜线上。

• 时间复杂度：最坏情况下为 O(N!)

def solve_n_queens(n):
    def is_safe