在NN的国际象棋棋盘上,如何放置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问题。
时间: 2024-04-03 16:34:26 浏览: 22
好的,我会尽力为您解答。以下是对您的问题的回答:
1. 编写第k号皇后是否可放置在棋盘上的判定算法:bool Placed(int k);
算法实现如下:
bool Placed(int k, int* pos)
{
for (int i = 0; i < k; i++)
{
if (pos[i] == pos[k] || abs(pos[i]-pos[k]) == abs(i-k))
return false;
}
return true;
}
其中pos数组存放已经放置好的皇后的位置信息,k表示当前需要判断的皇后的序号。如果第k个皇后与前面的皇后在同一列或者在对角线上(包括左上右下和右上左下两个方向),则返回false,否则返回true。
2. 编写实现前stop个皇后能否放置的随机算法bool nQueenLV(int stop);
算法实现如下:
bool nQueenLV(int stop, int* pos)
{
int N = stop;
int k = 0;
while (k >= 0 && k < N)
{
int count = 0;
for (int i = 0; i < N; i++)
{
pos[k] = i;
if (Placed(k, pos))
{
count++;
}
}
if (count > 0)
{
int r = rand() % count;
int j = 0;
for (int i = 0; i < N; i++)
{
pos[k] = i;
if (Placed(k, pos))
{
if (j == r)
{
break;
}
j++;
}
}
k++;
}
else
{
k--;
}
}
if (k == N)
{
return true;
}
else
{
return false;
}
}
其中pos数组存放已经放置好的皇后的位置信息,stop表示需要放置的皇后的个数。算法采用了随机化的策略:对于当前需要放置的皇后,先遍历所有可能的位置,计算出合法的位置个数count,然后随机选择其中一个位置进行放置。如果当前皇后有合法的位置可以放置,则将其放置在一个随机选择的合法位置上,并处理下一个皇后;如果当前皇后没有合法的位置可以放置,则回溯到上一个皇后,重新选择其它位置进行放置。
3. 编写实现后step到N号皇后能否放置的非递归回溯算法bool Backtrack(int step);
算法实现如下:
bool Backtrack(int step, int N, int* pos)
{
int k = step;
while (k >= 0 && k < N)
{
if (k == N-1 && Placed(k, pos))
{
return true;
}
if (k < N-1)
{
pos[k+1] = -1;
}
int i = pos[k] + 1;
while (i < N)
{
pos[k] = i;
if (Placed(k, pos))
{
break;
}
i++;
}
if (i < N)
{
k++;
}
else
{
pos[k] = -1;
k--;
}
}
return false;
}
其中pos数组存放已经放置好的皇后的位置信息,step表示需要从哪个皇后开始进行放置,N表示需要放置的皇后的个数。算法采用了非递归的回溯策略:对于当前需要放置的皇后,先将其位置向右移动一格,并检查是否可以放置,如果可以则处理下一个皇后;如果不行,则继续向右移动一格,直到找到一个合法的位置为止。如果当前皇后没有合法的位置可以放置,则回溯到上一个皇后,重新选择其它位置进行放置。
4. 编写bool nQueen()函数,调用2)和3)算法,将结果打印到文件(Queen.txt)
算法实现如下:
bool nQueen(int N, int stop, int step)
{
int* pos = new int[N];
for (int i = 0; i < N; i++)
{
pos[i] = -1;
}
bool ret1 = nQueenLV(stop, pos);
bool ret2 = Backtrack(step, N, pos);
ofstream fout("Queen.txt");
if (ret1)
{
fout << "随机算法可以放置" << stop << "个皇后" << endl;
for (int i = 0; i < stop; i++)
{
fout << pos[i]+1 << " ";
}
fout << endl;
}
else
{
fout << "随机算法不能放置" << stop << "个皇后" << endl;
}
if (ret2)
{
fout << "回溯算法可以放置从" << step+1 << "到" << N << "号皇后" << endl;
for (int i = step; i < N; i++)
{
fout << pos[i]+1 << " ";
}
fout << endl;
}
else
{
fout << "回溯算法不能放置从" << step+1 << "到" << N << "号皇后" << endl;
}
fout.close();
delete[] pos;
return ret1 && ret2;
}
其中N表示需要放置的皇后的个数,stop表示需要随机放置的皇后的个数,step表示从哪个皇后开始进行回溯放置。函数会调用2)和3)算法,将结果输出到文件Queen.txt中。
5. 实例N=12, stop=4, step=5,编写程序求解nQueen问题。
调用nQueen函数即可,代码如下:
nQueen(12, 4, 5);
程序会生成一个名为Queen.txt的文件,其中包含了随机算法和回溯算法的结果。根据您的需要,可以将N、stop、step修改为其它数值进行测试。