回溯算法：穷举搜索的系统方法

算法原理

回溯算法（Backtracking）是一种通过穷举来寻找所有解的算法。如果发现已不满足求解条件，就返回，尝试另一种可能。回溯是递归的副产品，只要有递归就会有回溯。

基本思想

1. 做出选择：在可能的选择中选择一个
2. 递归求解：在选择基础上求解子问题
3. 检查结果：如果子问题无解，撤销选择
4. 尝试其他：尝试其他可能的选择

C语言实现

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// N皇后问题
bool is_safe(int board[], int row, int col, int n) {
    for (int i = 0; i < row; i++) {
        // 检查列冲突和对角线冲突
        if (board[i] == col || 
            board[i] - i == col - row || 
            board[i] + i == col + row) {
            return false;
        }
    }
    return true;
}

bool solve_n_queens(int board[], int row, int n) {
    if (row == n) {
        return true; // 找到解
    }
    
    for (int col = 0; col < n; col++) {
        if (is_safe(board, row, col, n)) {
            board[row] = col; // 做选择
            
            if (solve_n_queens(board, row + 1, n)) {
                return true;
            }
            
            // 撤销选择（隐式回溯）
        }
    }
    
    return false;
}

// 数独求解
bool is_valid_sudoku(int board[9][9], int row, int col, int num) {
    // 检查行
    for (int x = 0; x < 9; x++) {
        if (board[row][x] == num) {
            return false;
        }
    }
    
    // 检查列
    for (int x = 0; x < 9; x++) {
        if (board[x][col] == num) {
            return false;
        }
    }
    
    // 检查3x3方格
    int start_row = row - row % 3;
    int start_col = col - col % 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i + start_row][j + start_col] == num) {
                return false;
            }
        }
    }
    
    return true;
}

bool solve_sudoku(int board[9][9]) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] == 0) {
                for (int num = 1; num <= 9; num++) {
                    if (is_valid_sudoku(board, row, col, num)) {
                        board[row][col] = num; // 做选择
                        
                        if (solve_sudoku(board)) {
                            return true;
                        }
                        
                        board[row][col] = 0; // 撤销选择
                    }
                }
                return false;
            }
        }
    }
    return true;
}

int main() {
    // N皇后问题测试
    int n = 8;
    int* board = (int*)malloc(n * sizeof(int));
    
    if (solve_n_queens(board, 0, n)) {
        printf("8皇后解: ");
        for (int i = 0; i < n; i++) {
            printf("(%d,%d) ", i, board[i]);
        }
        printf("\n");
    }
    
    free(board);
    return 0;
}

应用场景

1. 组合优化问题：N皇后、数独
2. 图着色问题：地图着色
3. 背包问题：0/1背包的暴力解法
4. 迷宫求解：找到所有可能路径

版权所有，如有侵权请联系我