C语言实现n皇后的算法

可以采用回溯法来实现n皇后问题的算法。该算法会在一个棋盘上放置n个皇后，使得每个皇后都不会互相攻击，即位于同一行、同一列或同一斜线的皇后数量都必须是1个。具体到算法实现上，我们可以采用逐列放置皇后的方式，每次选择一列，然后尝试在该列上放置皇后，如果能放置，则递归处理下一列；如果不能放置，则回溯到上一列，重新尝试放置皇后，直到找到所有的解。

以下是C语言的实现代码：

#include <stdio.h>

#define MAXN 1000 //最大皇后数

int n; //皇后数量
int column[MAXN]; //存储每一行皇后所在的列

//判断该位置是否可以放置皇后
int check(int row, int col)
{
    for(int i = 0; i < row; i++)
    {
        if(column[i] == col || abs(column[i] - col) == abs(i - row))
            return 0;
    }
    return 1;
}

//递归回溯求解n皇后问题
void nqueens(int row)
{
    if(row == n) //找到一个解
    {
        for(int i = 0; i < n; i++)
            printf("%d ", column[i]);
        printf("\n");
    }
    else
    {
        for(int j = 0; j < n; j++) //逐列放置皇后
        {
            if(check(row, j))
            {
                column[row] = j;
                nqueens(row + 1);
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    nqueens(0);
    return 0;
}

该算法的时间复杂度为O(n^n)，因为存在n^n种不同的摆放情况，需要逐一尝试。当n比较小时，该算法可以较快求解问题，但当n比较大时，需要考虑其他更为高效的算法。