LeetCode·51.N皇后·递归+回溯

链接：https://leetcode.cn/problems/n-queens/solution/-by-xun-ge-v-dn14/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
本题应该是回溯的经典题

首先来看一下皇后们的约束条件：

• 不能同行
• 不能同列
• 不能同斜线 （45度和135度角）

确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。
下面我用一个3 * 3 的***，将搜索过程抽象为一颗树，如图：

具体实现
我们定义一个n*n大小的棋盘，然后递归枚举棋盘上面每一个位置判断当前位置能不能成为皇后，能不能成为皇后的约束条件上面已经给出，如果当前位置不能成为皇后就直接跳过当前位置，如果当前位置能成为皇后，就重复上述步骤，直到枚举到最后一行为止 

大体为递归枚举每一列，每层递归枚举行中每一个元素 

代码注释超级详细
分为【直接修改】和【间接修改】

代码

【直接修改】：直接在棋盘上进行改动

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
 
bool isValid(char ** res, int row, int col, int n) {
    // 检查列
    for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (res[i][col] == 'Q') {
            return false;
        }
    }
    // 检查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (res[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (res[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
 
void dfs(char *** ans, int * returnSize, int ** returnColumnSizes, char ** res, int index, int n)
{ 
    //枚举到最后一行，保存当前棋盘，因为如果不能成为皇后就不能进入下一行
    //所以能到最后一行肯定是有效的
    if(index == n)
    {
        ans[(*returnSize)] = (char **)malloc(sizeof(char *) * n);
        for(int i = 0; i < n; i++)
        {
            ans[(*returnSize)][i] = (char *)malloc(sizeof(char) * (n+1));
            memcpy(ans[(*returnSize)][i], res[i], sizeof(char) * (n+1));
        }
        (*returnColumnSizes)[(*returnSize)++] = n;
        return;
    }
    //枚举当前行中每一个元素
    for(int i = 0; i < n; i++)
    {
        if(isValid(res, index, i, n) == true)//检查当前位置能不能放皇后
        {
            res[index][i] = 'Q';//可以直接放皇后
            dfs(ans, returnSize, returnColumnSizes, res, index+1, n);//进入下一行，重复当前步骤
            res[index][i] = '.';//回溯，进行判断下一个元素
        }
    }
    return ;
}
 
char *** solveNQueens(int n, int* returnSize, int** returnColumnSizes){
    char *** ans = (char ***)malloc(sizeof(char**) * 1000);
    *returnColumnSizes = (int *)malloc(sizeof(int) * 1000);//初始化变量
    *returnSize = 0;
    char ** res = (char **)malloc(sizeof(char *) * n);
    for(int i = 0; i < n; i++)//定义棋盘并初始化
    {
        res[i] = (char *)malloc(sizeof(char) * (n+1));
        memset(res[i], '.', sizeof(char) * n);
        res[i][n] = '\0';
    }
    //递归枚举每一个位置
    dfs(ans, returnSize, returnColumnSizes, res, 0, n);
 
    return ans;
}
 
 
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/n-queens/solution/-by-xun-ge-v-dn14/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

【间接修改】：利用数组保存皇后位置，棋盘不做修改 

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
bool isVaild(int* path, int row, int col) {
    /* 依次遍历当前行row的之前所有行 */
    for (int i = 0; i < row; i++) {
        /* path[i] == col 表示这一列上有其他皇后
         * row + col == path[i] + 1 表示右上角有其他皇后
         * row - col == i - path[i] 表示左上角有其他皇后
         */
        if (path[i] == col || row + col == path[i] + i || row - col == i - path[i]) {
            /* 出现皇后相互冲突，返回true */
            return true;
        }
    }
    /* 未出现皇后互相冲突，返回false */
    return false;
}
 
void backtrack(int n, int row, int* path, char*** res, int* returnSize) {
    /* 1、当前行数为n，表示已经找到了N皇后的一个解 */
    if (row == n) {
        /* 当前解的行数为n，为其分配空间 */
        res[*returnSize] = (char**)malloc(sizeof(char*) * n);
        for (int i = 0; i < n; i++) {
            /* 当前解的当前行的列数为n+1，因为存储的时字符串，所以需要一个'\0' 
             * 使用memset将当前解的当前行全部赋值为0
             */
            res[*returnSize][i] = (char*)calloc(n+1, sizeof(char));
            /* 将当前解的当前行全部赋值为'.' */
            memset(res[*returnSize][i], '.', n);
            /* 再将当前解的当前行中皇后为位置赋值为'Q' */
            res[*returnSize][i][path[i]] = 'Q';
        }
        /* 解的数量加一 */
        (*returnSize)++;
        /* 返回上一层决策树 */
        return;
    }
    /* 2、当前行数 < n，还未到达决策树的底层 */
    for (int j = 0; j < n; j++) {
        /* 排除当前行row的当前列j上是否发送皇后冲突 */
        if (isVaild(path, row, j)) {
            /* 发生冲突，跳过此列继续查找下一列 */
            continue;
        }
        /* 当前列j可以放置皇后 */
        path[row] = j;
        /* 进入下一层决策树，查找下一行的皇后位置 
         * 这里没有[选择]和[取消选择]是因为
         * 这里的[选择]就是当前行数row，而传入下一层决策树的[选择]就是row+1
         * 所以不许要[选择]和[取消选择]了
         */
        //row++;    /* [选择] */
        //backtrack(n, row, path, res, returnSize); /* 进入下一层决策树 */
        //row--;    /* [取消选择] */
        backtrack(n, row+1, path, res, returnSize);
    }
}
 
char*** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {
    /* 1、赋值解的个数，初值为0 */
    *returnSize = 0;
    /* 2、定义[路径]数组，用于存储一行中皇后的列位置下标 */
    int* path = (int*)calloc(n, sizeof(int));
    /* 3、定义返回数组 */
    char*** res = (char***)malloc(sizeof(char**) * n*n*n);
    /* 4、进行回溯查找 
     * 参数1：皇后的个数
     * 参数2：当前行数，从0行开始查找
     * 参数3: 路径数组path，用于存储当前行皇后所在位置；列下标
     * 参数4：返回数组，存储N皇后排列的解
     * 参数5：解的个数
     */
    backtrack(n, 0, path, res, returnSize);
    /* 5、分配用于存储解中列数的空间 */
    *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < (*returnSize); i++) {
        /* 解为NxN矩阵，每一行的列数均为N */
        (*returnColumnSizes)[i] = n;
    }
    /* 6、打印解的个数，用于调试 */
    //printf("the number of res is %d\n", *returnSize);
    /* 7、返回解数组 */
    return res;
}
 
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/n-queens/solution/-by-xun-ge-v-dn14/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。