一、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，用c语言编写程序求解nQueen问题。

好的，我知道了。这是一个经典的算法问题，我会尽力回答你的问题。

首先，我们来看第一个问题。判断第k个皇后是否可以放置在棋盘上，需要满足以下条件：

1. 第k个皇后的列不能与之前的皇后在同一列。
2. 第k个皇后的对角线不能与之前的皇后相交。

具体实现代码如下：

bool Placed(int k){
for(int i=1; i<k; i++){
if(pos[i]==pos[k] || abs(pos[i]-pos[k])==abs(i-k)){
return false;
}
}
return true;
}

其中，pos[i]表示第i个皇后放置在第pos[i]列。

接下来，我们来看第二个问题。实现前stop个皇后能否放置的随机算法，需要遵循以下步骤：

1. 初始化当前已放置的皇后数量为0。
2. 生成一个随机数x，表示将要放置第x个皇后。
3. 判断第x个皇后是否可以放置在棋盘上，如果可以，将其放置在棋盘上，更新已放置的皇后数量；否则，回到第2步生成一个新的随机数。
4. 重复步骤2和3，直到已放置的皇后数量达到stop或者无法再放置皇后。

具体实现代码如下：

bool nQueenLV(int stop){
int cnt=0;
while(cnt<stop){
int x = rand()%N+1;
pos[cnt+1] = x;
if(Placed(cnt+1)){
cnt++;
}
}
return cnt==stop;
}

其中，pos[i]表示第i个皇后放置在第pos[i]列。

接下来，我们来看第三个问题。实现后step到N号皇后能否放置的非递归回溯算法，需要遵循以下步骤：

1. 初始化当前已放置的皇后数量为step。
2. 从第step+1列开始，依次枚举每一个列，尝试将第step+1个皇后放置在该列上。
3. 判断第step+1个皇后是否可以放置在当前列上，如果可以，将其放置在棋盘上，更新已放置的皇后数量；否则，回到第2步枚举下一列。
4. 重复步骤2和3，直到已放置的皇后数量达到N或者无法再放置皇后。
5. 如果已放置的皇后数量达到N，表示找到了一组可行解；否则，回溯到上一个皇后位置，重新尝试放置皇后。

具体实现代码如下：

bool Backtrack(int step){
if(step==N){
return true;
}
for(int i=1; i<=N; i++){
pos[step+1] = i;
if(Placed(step+1)){
if(Backtrack(step+1)){
return true;
}
}
}
return false;
}

其中，pos[i]表示第i个皇后放置在第pos[i]列。

最后，我们来看第四个问题。实现nQueen函数，调用2）和3）算法，将结果打印到文件(Queen.txt)。具体实现代码如下：

bool nQueen(){
bool res = nQueenLV(4);
if(!res) return false;
res = Backtrack(4);
if(!res) return false;
ofstream fout("Queen.txt");
for(int i=1; i<=N; i++){
fout<<pos[i]<<" ";
}
fout.close();
return true;
}

最后，我们来看第五个问题。实例N=12，stop=4，step=5，用c语言编写程序求解nQueen问题。具体实现代码如下：

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>
using namespace std;

const int N = 12;
int pos[N+1];

bool Placed(int k){
for(int i=1; i<k; i++){
if(pos[i]==pos[k] || abs(pos[i]-pos[k])==abs(i-k)){
return false;
}
}
return true;
}

bool nQueenLV(int stop){
int cnt=0;
while(cnt<stop){
int x = rand()%N+1;
pos[cnt+1] = x;
if(Placed(cnt+1)){
cnt++;
}
}
return cnt==stop;
}

bool Backtrack(int step){
if(step==N){
return true;
}
for(int i=1; i<=N; i++){
pos[step+1] = i;
if(Placed(step+1)){
if(Backtrack(step+1)){
return true;
}
}
}
return false;
}

bool nQueen(){
bool res = nQueenLV(4);
if(!res) return false;
res = Backtrack(4);
if(!res) return false;
ofstream fout("Queen.txt");
for(int i=1; i<=N; i++){
fout<<pos[i]<<" ";
}
fout.close();
return true;
}

int main(){
nQueen();
return 0;
}