一、 nQueen皇后问题 在NN的国际象棋棋盘上，如何放置N个皇后，使其不相互攻击。 要求： 1） 编写第k号皇后是否可放置在棋盘上的判定算法：bool Placed(int k); 2） 编写实现前stop个皇后能否放置的随机算法bool nQueenLV(int stop); 3） 编写实现后step到N号皇后能否放置的非递归回溯算法bool Backtrack(int step); 4） 编写bool nQueen()函数，调用2）和3）算法，将结果打印到文件(Queen.txt) 5） 实例N=12, stop=4, step=5，编写程序求解nQueen问题。，用C语言程序实现

以下是C语言程序实现nQueen问题：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 12
int x[N+1],stop,step;
bool Placed(int k) // 判断第k号皇后是否可放置
{
    for(int i=1;i<k;i++)
    {
        if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))
            return false;
    }
    return true;
}
bool nQueenLV(int stop) // 实现前stop个皇后能否放置的随机算法
{
    srand((unsigned)time(NULL));
    for(int i=1;i<=stop;i++)
    {
        x[i]=rand()%stop+1;
    }
    for(int i=1;i<=stop;i++)
    {
        if(!Placed(i))
            return false;
    }
    return true;
}
bool Backtrack(int step) // 实现后step到N号皇后能否放置的非递归回溯算法
{
    int k=step;
    while(k<=N)
    {
        x[k]++;
        while(x[k]<=N&&!Placed(k))
            x[k]++;
        if(x[k]<=N&&k==N)
            return true;
        if(x[k]<=N&&k<N)
            k++;
        else
        {
            x[k]=0;
            k--;
            while(x[k]==N)
                k--;
            if(k==0)
                return false;
        }
    }
    return false;
}
bool nQueen() // 调用2）和3）算法，将结果打印到文件(Queen.txt)
{
    FILE *fp;
    if((fp=fopen("Queen.txt","w"))==NULL)
        return false;
    if(!nQueenLV(stop))
    {
        fprintf(fp,"前%d个皇后不能放置\n",stop);
        return false;
    }
    if(!Backtrack(step))
    {
        fprintf(fp,"后%d到%d号皇后不能放置\n",step,N);
        return false;
    }
    fprintf(fp,"皇后放置方案如下:\n");
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(x[i]==j)
                fprintf(fp,"O");
            else
                fprintf(fp,"X");
        }
        fprintf(fp,"\n");
    }
    fclose(fp);
    return true;
}
int main()
{
    stop=4;
    step=5;
    nQueen();
    return 0;
}

在上述代码中，我们先定义了一个长度为N+1的数组x，用来存储皇后所在的列数。然后，我们实现了Placed函数，用来判断第k号皇后是否可以放置。其实现原理是：皇后放在第k行第x[k]列，如果和前面的皇后在同一列或同一条对角线上，则返回false。否则返回true。

接着，我们实现了nQueenLV函数，用来实现前stop个皇后能否放置的随机算法。它的实现原理是：随机生成前stop个皇后所在的列数，然后依次检查它们是否可以放置。如果都可以放置，则返回true；否则返回false。

然后，我们实现了Backtrack函数，用来实现后step到N号皇后能否放置的非递归回溯算法。它的实现原理是：从第step号皇后开始，依次放在下一列，然后判断是否可以放置。如果可以放置，则放置下一个皇后；否则回溯到上一个皇后，将皇后移动到下一列再次判断。直到找到所有皇后的放置方案，或者找不到任何方案。

最后，我们实现了nQueen函数，用来调用2）和3）算法，将结果打印到文件(Queen.txt)中。在函数中，我们先判断前stop个皇后能否放置，然后判断后step到N号皇后能否放置。如果都能放置，则将所有皇后的放置方案打印到文件中。

在main函数中，我们设置stop=4，step=5，然后调用nQueen函数。