文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >Rust算法——回溯算法基础——N皇后与全排列

Rust算法——回溯算法基础——N皇后与全排列

作者头像
红目香薰
发布于 2025-12-16 16:41:28
发布于 2025-12-16 16:41:28
110
举报
文章被收录于专栏：CSDNToQQCodeCSDNToQQCode

回溯算法（Backtracking）是一种通过探索所有可能的候选解来找出所有解的算法。当探索到某一步时，如果发现这个选择不能得到有效解，就回退一步重新选择。本文将详细介绍回溯算法的核心思想，并通过 N 皇后问题和全排列问题来深入理解。

在这里插入图片描述
在这里插入图片描述

目录

  • 1. 回溯算法概述
  • 2. 回溯算法模板
  • 3. 全排列问题
  • 4. N 皇后问题
  • 5. 回溯算法优化
  • 6. 更多回溯问题
  • 7. 复杂度分析
  • 8. 扩展练习

1. 回溯算法概述

1.1 什么是回溯算法？

回溯算法是一种试探性的搜索算法，它通过逐步构建解，当发现当前路径不可能得到解时，就回退到上一步，尝试其他可能。

核心思想：

  • 尝试：在当前状态下尝试所有可能的选择
  • 验证：检查当前选择是否有效
  • 递归：如果有效，继续下一步
  • 回溯：如果无效或已找到解，回退并尝试其他选择
1.2 回溯算法的特点
  • ✅ 系统性搜索：系统地探索所有可能的解
  • ✅ 剪枝优化：可以提前剪掉不可能的分支
  • ✅ 适用场景：组合问题、排列问题、子集问题、约束满足问题
1.3 回溯 vs 递归

回溯是递归的一种应用，但更强调：

  • 状态恢复：回退时需要恢复之前的状态
  • 剪枝：提前终止不可能的分支
  • 解空间树：在解空间树中搜索

2. 回溯算法模板

2.1 通用回溯模板
代码语言：javascript
复制
fn backtrack(当前状态, 路径, 结果集) {
    // 1. 终止条件
    if 满足终止条件 {
        结果集.push(路径.clone());
        return;
    }
    
    // 2. 遍历所有可能的选择
    for 选择 in 所有可能的选择 {
        // 3. 做选择（修改状态）
        路径.push(选择);
        修改状态;
        
        // 4. 递归（进入下一层）
        backtrack(新状态, 路径, 结果集);
        
        // 5. 撤销选择（恢复状态）
        路径.pop();
        恢复状态;
    }
}
2.2 Rust 实现模板
代码语言：javascript
复制
/// 回溯算法通用模板（Rust 风格）
fn backtrack_template<T: Clone>(
    state: &mut Vec<T>,
    choices: &[T],
    result: &mut Vec<Vec<T>>,
    is_valid: fn(&[T]) -> bool,
) {
    // 终止条件：找到完整解
    if state.len() == choices.len() {
        if is_valid(state) {
            result.push(state.clone());
        }
        return;
    }
    
    // 遍历所有可能的选择
    for choice in choices {
        // 剪枝：如果当前选择不合法，跳过
        if !is_valid_choice(state, choice) {
            continue;
        }
        
        // 做选择
        state.push(choice.clone());
        
        // 递归
        backtrack_template(state, choices, result, is_valid);
        
        // 撤销选择（回溯）
        state.pop();
    }
}

3. 全排列问题

3.1 问题描述

全排列问题： 给定一个不含重复数字的数组，返回其所有可能的全排列。

示例：

  • 输入：[1, 2, 3]
  • 输出：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
3.2 基础实现
代码语言：javascript
复制
/// 全排列问题 - 基础回溯实现
fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut path = Vec::new();
    let mut used = vec![false; nums.len()];
    
    fn backtrack(
        nums: &[i32],
        path: &mut Vec<i32>,
        used: &mut Vec<bool>,
        result: &mut Vec<Vec<i32>>,
    ) {
        // 终止条件：路径长度等于数组长度
        if path.len() == nums.len() {
            result.push(path.clone());
            return;
        }
        
        // 遍历所有可能的选择
        for i in 0..nums.len() {
            // 剪枝：如果数字已使用，跳过
            if used[i] {
                continue;
            }
            
            // 做选择
            path.push(nums[i]);
            used[i] = true;
            
            // 递归
            backtrack(nums, path, used, result);
            
            // 撤销选择（回溯）
            path.pop();
            used[i] = false;
        }
    }
    
    backtrack(&nums, &mut path, &mut used, &mut result);
    result
}

fn main() {
    let nums = vec![1, 2, 3];
    let result = permute(nums);
    println!("全排列结果：");
    for perm in &result {
        println!("{:?}", perm);
    }
    println!("共 {} 种排列", result.len());
}
在这里插入图片描述
在这里插入图片描述

输出：

代码语言：javascript
复制
全排列结果：
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
共 6 种排列
3.3 使用交换的实现
代码语言：javascript
复制
/// 全排列 - 使用交换实现（更节省空间）
fn permute_swap(nums: &mut Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    
    fn backtrack(nums: &mut Vec<i32>, start: usize, result: &mut Vec<Vec<i32>>) {
        // 终止条件
        if start == nums.len() {
            result.push(nums.clone());
            return;
        }
        
        // 从 start 开始，依次与后面的元素交换
        for i in start..nums.len() {
            // 做选择：交换
            nums.swap(start, i);
            
            // 递归
            backtrack(nums, start + 1, result);
            
            // 撤销选择：交换回来
            nums.swap(start, i);
        }
    }
    
    backtrack(nums, 0, &mut result);
    result
}

fn main() {
    let mut nums = vec![1, 2, 3];
    let result = permute_swap(&mut nums);
    println!("使用交换实现的全排列：");
    for perm in &result {
        println!("{:?}", perm);
    }
}
3.4 处理重复元素
代码语言：javascript
复制
/// 全排列 - 处理重复元素
fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut nums = nums;
    nums.sort(); // 排序以便去重
    
    let mut result = Vec::new();
    let mut path = Vec::new();
    let mut used = vec![false; nums.len()];
    
    fn backtrack(
        nums: &[i32],
        path: &mut Vec<i32>,
        used: &mut Vec<bool>,
        result: &mut Vec<Vec<i32>>,
    ) {
        if path.len() == nums.len() {
            result.push(path.clone());
            return;
        }
        
        for i in 0..nums.len() {
            // 剪枝1：已使用
            if used[i] {
                continue;
            }
            
            // 剪枝2：重复元素，只使用第一个未使用的
            // 如果当前元素与前一个相同，且前一个未使用，跳过
            if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] {
                continue;
            }
            
            path.push(nums[i]);
            used[i] = true;
            backtrack(nums, path, used, result);
            path.pop();
            used[i] = false;
        }
    }
    
    backtrack(&nums, &mut path, &mut used, &mut result);
    result
}

fn main() {
    let nums = vec![1, 1, 2];
    let result = permute_unique(nums);
    println!("含重复元素的全排列：");
    for perm in &result {
        println!("{:?}", perm);
    }
    // 输出：[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
}

4. N 皇后问题

4.1 问题描述

N 皇后问题： 在 n×n 的棋盘上放置 n 个皇后，使得它们不能相互攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。

示例：

  • 4 皇后问题有 2 种解
  • 8 皇后问题有 92 种解
4.2 基础实现
代码语言：javascript
复制
/// N 皇后问题 - 基础回溯实现
fn solve_n_queens(n: usize) -> Vec<Vec<String>> {
    let mut result = Vec::new();
    let mut board = vec![vec!['.'; n]; n];
    
    fn is_valid(board: &[Vec<char>], row: usize, col: usize) -> bool {
        let n = board.len();
        
        // 检查列
        for i in 0..row {
            if board[i][col] == 'Q' {
                return false;
            }
        }
        
        // 检查左上对角线
        let mut i = row as i32 - 1;
        let mut j = col as i32 - 1;
        while i >= 0 && j >= 0 {
            if board[i as usize][j as usize] == 'Q' {
                return false;
            }
            i -= 1;
            j -= 1;
        }
        
        // 检查右上对角线
        let mut i = row as i32 - 1;
        let mut j = col as i32 + 1;
        while i >= 0 && j < n as i32 {
            if board[i as usize][j as usize] == 'Q' {
                return false;
            }
            i -= 1;
            j += 1;
        }
        
        true
    }
    
    fn backtrack(
        board: &mut Vec<Vec<char>>,
        row: usize,
        result: &mut Vec<Vec<String>>,
    ) {
        let n = board.len();
        
        // 终止条件：所有行都放置了皇后
        if row == n {
            let solution: Vec<String> = board
                .iter()
                .map(|row| row.iter().collect())
                .collect();
            result.push(solution);
            return;
        }
        
        // 尝试在当前行的每一列放置皇后
        for col in 0..n {
            // 剪枝：检查是否可以放置
            if !is_valid(board, row, col) {
                continue;
            }
            
            // 做选择
            board[row][col] = 'Q';
            
            // 递归：处理下一行
            backtrack(board, row + 1, result);
            
            // 撤销选择
            board[row][col] = '.';
        }
    }
    
    backtrack(&mut board, 0, &mut result);
    result
}

fn main() {
    let n = 4;
    let solutions = solve_n_queens(n);
    println!("{} 皇后问题的解（共 {} 种）：", n, solutions.len());
    for (i, solution) in solutions.iter().enumerate() {
        println!("\n解 {}:", i + 1);
        for row in solution {
            println!("{}", row);
        }
    }
}

输出：

代码语言：javascript
复制
4 皇后问题的解（共 2 种）：

解 1:
.Q..
...Q
Q...
..Q.

解 2:
..Q.
Q...
...Q
.Q..
4.3 优化实现（使用集合）
代码语言：javascript
复制
/// N 皇后问题 - 优化实现（使用集合记录冲突）
fn solve_n_queens_optimized(n: usize) -> Vec<Vec<String>> {
    let mut result = Vec::new();
    let mut queens = Vec::new(); // 记录每行皇后的列位置
    let mut cols = std::collections::HashSet::new();
    let mut diag1 = std::collections::HashSet::new(); // 主对角线
    let mut diag2 = std::collections::HashSet::new(); // 副对角线
    
    fn backtrack(
        row: usize,
        n: usize,
        queens: &mut Vec<usize>,
        cols: &mut std::collections::HashSet<usize>,
        diag1: &mut std::collections::HashSet<i32>,
        diag2: &mut std::collections::HashSet<i32>,
        result: &mut Vec<Vec<String>>,
    ) {
        if row == n {
            // 构建解
            let solution: Vec<String> = (0..n)
                .map(|r| {
                    (0..n)
                        .map(|c| if queens[r] == c { 'Q' } else { '.' })
                        .collect()
                })
                .collect();
            result.push(solution);
            return;
        }
        
        for col in 0..n {
            let d1 = row as i32 - col as i32;
            let d2 = row as i32 + col as i32;
            
            // 剪枝：检查冲突
            if cols.contains(&col) || diag1.contains(&d1) || diag2.contains(&d2) {
                continue;
            }
            
            // 做选择
            queens.push(col);
            cols.insert(col);
            diag1.insert(d1);
            diag2.insert(d2);
            
            // 递归
            backtrack(row + 1, n, queens, cols, diag1, diag2, result);
            
            // 撤销选择
            queens.pop();
            cols.remove(&col);
            diag1.remove(&d1);
            diag2.remove(&d2);
        }
    }
    
    backtrack(0, n, &mut queens, &mut cols, &mut diag1, &mut diag2, &mut result);
    result
}

fn main() {
    let n = 8;
    let solutions = solve_n_queens_optimized(n);
    println!("{} 皇后问题共有 {} 种解", n, solutions.len());
}
4.4 可视化 N 皇后解
代码语言：javascript
复制
/// 可视化 N 皇后解
fn print_queens_solution(solution: &[String]) {
    let n = solution.len();
    
    // 打印顶部边框
    println!("┌{}┐", "─".repeat(n * 2 + 1));
    
    for (i, row) in solution.iter().enumerate() {
        print!("│ ");
        for (j, ch) in row.chars().enumerate() {
            if ch == 'Q' {
                print!("♛ ");
            } else {
                if (i + j) % 2 == 0 {
                    print!("  ");
                } else {
                    print!("█ ");
                }
            }
        }
        println!("│");
    }
    
    // 打印底部边框
    println!("└{}┘", "─".repeat(n * 2 + 1));
}

fn main() {
    let solutions = solve_n_queens(4);
    println!("4 皇后问题的解：\n");
    for (i, solution) in solutions.iter().enumerate() {
        println!("解 {}:", i + 1);
        print_queens_solution(solution);
        println!();
    }
}

5. 回溯算法优化

5.1 剪枝优化

剪枝是回溯算法最重要的优化手段：

代码语言：javascript
复制
/// 剪枝优化示例：数独求解
fn is_valid_sudoku(board: &[Vec<char>], row: usize, col: usize, num: char) -> bool {
    let n = 9;
    
    // 检查行
    for j in 0..n {
        if board[row][j] == num {
            return false;
        }
    }
    
    // 检查列
    for i in 0..n {
        if board[i][col] == num {
            return false;
        }
    }
    
    // 检查 3x3 宫格
    let start_row = (row / 3) * 3;
    let start_col = (col / 3) * 3;
    for i in start_row..start_row + 3 {
        for j in start_col..start_col + 3 {
            if board[i][j] == num {
                return false;
            }
        }
    }
    
    true
}
5.2 记忆化优化

对于有重叠子问题的情况，可以使用记忆化：

代码语言：javascript
复制
use std::collections::HashMap;

/// 记忆化回溯：计算路径数量
fn unique_paths_with_memo(
    m: i32,
    n: i32,
    memo: &mut HashMap<(i32, i32), i32>,
) -> i32 {
    if m == 1 || n == 1 {
        return 1;
    }
    
    if let Some(&result) = memo.get(&(m, n)) {
        return result;
    }
    
    let result = unique_paths_with_memo(m - 1, n, memo)
        + unique_paths_with_memo(m, n - 1, memo);
    memo.insert((m, n), result);
    result
}
5.3 迭代加深

对于深度不确定的问题，可以使用迭代加深：

代码语言：javascript
复制
/// 迭代加深搜索
fn iddfs(start: State, target: State, max_depth: usize) -> Option<Vec<State>> {
    for depth in 0..=max_depth {
        let mut visited = std::collections::HashSet::new();
        if let Some(path) = dfs_limited(start.clone(), target.clone(), depth, &mut visited) {
            return Some(path);
        }
    }
    None
}

6. 更多回溯问题

6.1 子集问题
代码语言：javascript
复制
/// 子集问题：返回所有可能的子集
fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut path = Vec::new();
    
    fn backtrack(
        nums: &[i32],
        start: usize,
        path: &mut Vec<i32>,
        result: &mut Vec<Vec<i32>>,
    ) {
        // 每个节点都是解
        result.push(path.clone());
        
        for i in start..nums.len() {
            path.push(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.pop();
        }
    }
    
    backtrack(&nums, 0, &mut path, &mut result);
    result
}

fn main() {
    let nums = vec![1, 2, 3];
    let result = subsets(nums);
    println!("子集：");
    for subset in &result {
        println!("{:?}", subset);
    }
    // 输出：[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]
}
6.2 组合问题
代码语言：javascript
复制
/// 组合问题：从 n 个数中选 k 个
fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut path = Vec::new();
    
    fn backtrack(
        start: i32,
        n: i32,
        k: i32,
        path: &mut Vec<i32>,
        result: &mut Vec<Vec<i32>>,
    ) {
        // 终止条件
        if path.len() == k as usize {
            result.push(path.clone());
            return;
        }
        
        // 剪枝：剩余元素不足以构成 k 个
        if (n - start + 1) < (k - path.len() as i32) {
            return;
        }
        
        for i in start..=n {
            path.push(i);
            backtrack(i + 1, n, k, path, result);
            path.pop();
        }
    }
    
    backtrack(1, n, k, &mut path, &mut result);
    result
}
6.3 单词搜索
代码语言：javascript
复制
/// 单词搜索：在二维网格中搜索单词
fn exist(board: Vec<Vec<char>>, word: String) -> bool {
    let word: Vec<char> = word.chars().collect();
    let mut visited = vec![vec![false; board[0].len()]; board.len()];
    
    fn backtrack(
        board: &[Vec<char>],
        word: &[char],
        visited: &mut Vec<Vec<bool>>,
        row: usize,
        col: usize,
        index: usize,
    ) -> bool {
        // 终止条件：找到完整单词
        if index == word.len() {
            return true;
        }
        
        // 边界检查
        if row >= board.len() || col >= board[0].len() {
            return false;
        }
        
        // 已访问或不匹配
        if visited[row][col] || board[row][col] != word[index] {
            return false;
        }
        
        // 做选择
        visited[row][col] = true;
        
        // 四个方向搜索
        let directions = [(0, 1), (0, -1), (1, 0), (-1, 0)];
        for (dr, dc) in &directions {
            let new_row = row as i32 + dr;
            let new_col = col as i32 + dc;
            if new_row >= 0 && new_col >= 0 {
                if backtrack(
                    board,
                    word,
                    visited,
                    new_row as usize,
                    new_col as usize,
                    index + 1,
                ) {
                    return true;
                }
            }
        }
        
        // 撤销选择
        visited[row][col] = false;
        false
    }
    
    // 从每个位置开始搜索
    for i in 0..board.len() {
        for j in 0..board[0].len() {
            if backtrack(&board, &word, &mut visited, i, j, 0) {
                return true;
            }
        }
    }
    
    false
}

7. 复杂度分析

7.1 时间复杂度

全排列问题：

  • 时间复杂度：O(n × n!)
  • 共有 n! 种排列，每种排列需要 O(n) 时间构建

N 皇后问题：

  • 时间复杂度：O(n!)
  • 最坏情况下需要探索所有可能的放置方式

子集问题：

  • 时间复杂度：O(2^n)
  • 共有 2^n 个子集
7.2 空间复杂度
  • 递归栈深度：O(n) - n 为问题规模
  • 存储解的空间：取决于解的个数
  • 辅助空间：O(n) - 用于标记已访问等
7.3 性能对比
代码语言：javascript
复制
use std::time::Instant;

fn benchmark_backtrack() {
    println!("回溯算法性能测试：\n");
    
    // 测试全排列
    println!("全排列（n = 8）：");
    let start = Instant::now();
    let result = permute((1..=8).collect());
    let duration = start.elapsed();
    println!("  结果数: {}", result.len());
    println!("  耗时: {:?}\n", duration);
    
    // 测试 N 皇后
    println!("N 皇后（n = 8）：");
    let start = Instant::now();
    let result = solve_n_queens_optimized(8);
    let duration = start.elapsed();
    println!("  结果数: {}", result.len());
    println!("  耗时: {:?}\n", duration);
}

8. 扩展练习

练习 1：数独求解器

实现一个数独求解器，使用回溯算法填充 9×9 的数独网格。

练习 2：括号生成

生成 n 对有效括号的所有组合。例如 n=3，输出：["((()))", "(()())", "(())()", "()(())", "()()()"]

练习 3：电话号码字母组合

给定一个仅包含数字 2-9 的字符串，返回所有可能的字母组合（手机键盘映射）。

练习 4：分割回文串

给定一个字符串，将字符串分割成一些子串，使每个子串都是回文串。返回所有可能的分割方案。

练习 5：复原 IP 地址

给定一个只包含数字的字符串，返回所有可能的有效 IP 地址。

练习 6：组合总和

给定一个无重复元素的数组和一个目标数，找出所有可以使数字和为目标数的组合。

总结

通过本章学习，你应该掌握：

✅ 回溯算法的核心思想 ✅ 回溯算法的通用模板 ✅ 全排列问题的多种实现 ✅ N 皇后问题的解法 ✅ 剪枝优化技巧 ✅ 复杂度分析方法

关键要点：

  • 回溯 = 递归 + 状态恢复
  • 剪枝是提高效率的关键
  • 理解解空间树的结构
  • 掌握做选择和撤销选择的时机

回溯算法适用场景：

  • 组合问题
  • 排列问题
  • 子集问题
  • 约束满足问题
  • 搜索问题
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-11-07，如有侵权请联系 cloudcommunity@tencent.com 删除
递归
基础
算法
优化
rust

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

递归
基础
算法
优化
rust
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 目录
  • 1. 回溯算法概述
    • 1.1 什么是回溯算法？
    • 1.2 回溯算法的特点
    • 1.3 回溯 vs 递归
  • 2. 回溯算法模板
    • 2.1 通用回溯模板
    • 2.2 Rust 实现模板
  • 3. 全排列问题
    • 3.1 问题描述
    • 3.2 基础实现
    • 3.3 使用交换的实现
    • 3.4 处理重复元素
  • 4. N 皇后问题
    • 4.1 问题描述
    • 4.2 基础实现
    • 4.3 优化实现（使用集合）
    • 4.4 可视化 N 皇后解
  • 5. 回溯算法优化
    • 5.1 剪枝优化
    • 5.2 记忆化优化
    • 5.3 迭代加深
  • 6. 更多回溯问题
    • 6.1 子集问题
    • 6.2 组合问题
    • 6.3 单词搜索
  • 7. 复杂度分析
    • 7.1 时间复杂度
    • 7.2 空间复杂度
    • 7.3 性能对比
  • 8. 扩展练习
    • 练习 1：数独求解器
    • 练习 2：括号生成
    • 练习 3：电话号码字母组合
    • 练习 4：分割回文串
    • 练习 5：复原 IP 地址
    • 练习 6：组合总和
  • 总结
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论