代码随想录算法训练营第二十五天|Day25 回溯算法

N皇后

思路

char ***ans;
char **path;
int ansTop, pathTop;
void copyPath(int n) {
    char **tempPath = (char**)malloc(sizeof(char*) * pathTop);
    int i;
    for(i = 0; i < pathTop; ++i) {
        tempPath[i] = (char*)malloc(sizeof(char) * n + 1);
        int j;
        for(j = 0; j < n; ++j)
            tempPath[i][j] = path[i][j];
        tempPath[i][j] = '\0';

    }
    ans[ansTop++] = tempPath;
}
int isValid(int x, int y, int n) {
    int i, j;
    for(i = 0; i < n; ++i) {
        if(path[y][i] == 'Q' || path[i][x] == 'Q')
            return 0;
    }
    i = y - 1;
    j = x - 1;
    while(i >= 0 && j >= 0) {
        if(path[i][j] == 'Q')
            return 0;
        --i, --j;
    }

    i = y + 1;
    j = x + 1;
    while(i < n && j < n) {
        if(path[i][j] == 'Q')
            return 0;
        ++i, ++j;
    }
    i = y - 1;
    j = x + 1;
    while(i >= 0 && j < n) {
        if(path[i][j] == 'Q')
            return 0;
        --i, ++j;
    }
    i = y + 1;
    j = x -1;
    while(j >= 0 && i < n) {
        if(path[i][j] == 'Q')
            return 0;
        ++i, --j;
    }
    return 1;
}
void backTracking(int n, int depth) {
    if(pathTop == n) {
        copyPath(n);
        return;
    }
    int i;
    for(i = 0; i < n; ++i) {
           if(isValid(i, depth, n)) {
           path[depth][i] = 'Q';
            ++pathTop;
            backTracking(n, depth + 1);
            path[depth][i] = '.';
            --pathTop;
        }
    }
}
void initPath(int n) {
    int i, j;
    for(i = 0; i < n; i++) {
        path[i] = (char*)malloc(sizeof(char) * n + 1);
        for(j = 0; j < n; j++)
            path[i][j] = '.';
        path[i][j] = '\0';
    }
}

char *** solveNQueens(int n, int* returnSize, int** returnColumnSizes){
    ans = (char***)malloc(sizeof(char**) * 400);
    path = (char**)malloc(sizeof(char*) * n);
    ansTop = pathTop = 0;
    initPath(n);
    backTracking(n, 0);
    *returnSize = ansTop;
    int i; 
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    for(i = 0; i < ansTop; ++i) {
        (*returnColumnSizes)[i] = n;
    }
    return ans;
}

学习反思

解决N皇后问题的回溯算法实现。首先定义了ans和path两个全局变量，用于存储结果和当前路径。ans是一个三维字符数组，表示所有解的集合。path是一个二维字符数组，表示当前路径的棋盘状态。copyPath函数用于将path中的元素复制到ans中。首先根据pathTop的大小动态分配tempPath的空间，然后逐个复制path中的元素到tempPath中，并在最后加入'\0'作为字符串结尾。完成复制后，将tempPath赋值给ans[ansTop]，并将ansTop自增1。isValid函数用于判断当前位置是否有效。首先通过两个for循环检查同一行和同一列是否有皇后，如果有则返回0表示无效。然后通过四个while循环检查两个斜角方向是否有皇后，如果有则返回0表示无效。最后返回1表示有效。backTracking函数是核心递归函数，用于将皇后放置到棋盘上。首先判断pathTop的大小是否等于n，如果是则说明path中已经有n个皇后，将path复制到ans中，然后返回上一层。否则，遍历当前行的每个位置，如果当前位置有效，则将皇后放置到该位置，然后调用backTracking函数递归下一行，递归完成后进行回溯，将当前位置的皇后移除，继续遍历下一个位置。initPath函数用于初始化path数组，将所有元素设为'.'。首先通过两个for循环分别为path中的每个char*开辟空间，并将所有字符设为'.'。在每个字符串的结尾加入'\0'作为字符串结尾。solveNQueens函数是整体的解决函数。首先初始化ans、path、ansTop和pathTop等变量。然后调用initPath函数初始化path数组。接着调用backTracking函数进行回溯算法。最后设置返回数组的大小和每个解的列数，并返回ans数组。这段代码的时间复杂度为O(n!)。

解数独

bool isValid(char** board, int row, int col, int k) {
    for (int i = 0; i < 9; i++) {
        if (board[i][col] == k) {
            return false;
        }
    }
    for (int j = 0; j < 9; j++) {
        if (board[row][j] == k) {
            return false;
        }
    }
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) {
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == k) {
                return false;
            }
        }
    }
    return true;
}

bool backtracking(char** board, int boardSize, int* boardColSize) {
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < *boardColSize; j++) {
            /* 遇到数字跳过 */
            if (board[i][j] != '.') {
                continue;
            }
            for (int k = '1'; k <= '9'; k++) {
                if (isValid(board, i, j, k)) {
                    board[i][j] = k;
                    if (backtracking(board, boardSize, boardColSize)) {
                        return true;
                    }
                    board[i][j] = '.';
                }
            }
            return false;
        }
    }
    return true;
}
void solveSudoku(char** board, int boardSize, int* boardColSize) {
    bool res = backtracking(board, boardSize, boardColSize);
}