TOP101题解 | BM59#N皇后问题#

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

/***************************************************************************
* @param queue 数组
* @param row 行号即queue下标
* @param column 列大小,为n
* @return bool型
***************************************************************************/
bool IsValid(int* queue, int row, int column)
{
    bool result = true;

    /*检查当前皇后所在行之前的皇后*/
    for(int i = 0; i < row; i++)
    {
        /*皇后同行或者斜线*/
        if(queue[i] == column || abs(row - i) == abs(column - queue[i]))
        {
            result = false;
            break;
        }
    }
    return result;
}


/***************************************************************************
* @param queue 数组
* @param row 当前在第row行摆放皇后,即queue下标
* @param n 棋盘的大小
* @param result 摆放结果
* @return int整型
***************************************************************************/
void backtrack(int* queue, int row, int n, int* result)
{
    if(row == n)
    {
        (*result)++;
        return;
    }
    else 
    {
        for(int column = 0; column < n; column++)
        {
            if(IsValid(queue, row, column))
            {
                queue[row] = column;
                /*在下一行继续摆放皇后*/
                backtrack(queue, row + 1, n, result);
            }
        }
    }
}


/***********************************************************************************************************
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.27
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * 
 * @brief
 *N皇后问题是一个经典的递归回溯问题，要求在 n * n 的棋盘上放置 n 个皇后
 *使得每个皇后都不在同一行、同一列、同一对角线上。可以通过回溯的方式来解决这个问题。
 *
 *在回溯算法中，我们逐行放置皇后，每次放置时，检查当前位置是否和之前的皇后位置产生冲突
 *如果冲突则回溯到上一行重新选择位置。如果能够成功地放置 n 个皇后，就计数一种解法。
 *
 *以下是基于回溯算法的 N 皇后问题的思路：
 *
 *1.创建一个大小为 n 的一维数组 queens，其中 queens[i] 表示第 i 行的皇后所在的列位置。
 *2.从第一行开始放置皇后，遍历每个列，检查当前位置是否和之前的皇后位置冲突，如果不冲突则继续放置下一行的皇后。
 *3.当放置到最后一行时，表示成功放置了一个皇后组合，计数器加一。
 *4.回溯到上一行，继续尝试下一个位置，直到所有的组合都尝试完毕。
 * 
 * @param n int整型 the n
 * @return int整型
***********************************************************************************************************/
int Nqueen(int n ) 
{
    // write code here
    int* queue = malloc(n * sizeof(int));
    int result = 0;
    backtrack(queue, 0, n, &result);

    return result;
}