admin管理员组文章数量:1531667
2024年5月1日发(作者：)
实验题目
回溯法实现8皇后问题
实验要求
a.掌握递归回溯算法的基本思想。
b.学习掌握应用面向对象通用回溯程序框架解决实际问题。 提
高面向对象编程的技能。
实验内容（问题描述、算法设计、算法效率）
回溯法实现8皇后问题
a.问题描述：在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的
规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。N后问题等
价于在n*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同
一斜线上。
b.算法设计：
用n元组x[1；n]表示n后问题的解。其中，x[i]表示皇后i放置在棋盘的第
i行的第x[i]列。由于不容许将2个皇后放在同一列上，所以解向量中的x[i]互不
相同。2个皇后不能放在同一斜线上是问题的隐约束。对于一般的n后问题，这
一隐约束条件可以化成显约束的形式。如果将n*n 格的棋盘看做二维方阵，其
行号从上到下，列号从左到右依次编号为1,2，...n。从棋盘左上角到右下角的主
对角线及其平行线（即斜率为-1的各斜线）上，2个下标值的差（行号-列号）
值相等。同理，斜率为+1的每条斜线上，2个下标值的和（行号+列号）值相等。
因此，若2个皇后放置的位置分别是（i,j）和（k,l）,且 i-j = k -l 或 i+j = k+l，
则说明这2个皇后处于同一斜线上。以上2个方程分别等价于i-k = j-l 和 i-k =l-j。
由此可知，只要|i-k|=|l-j|成立，就表明2个皇后位于同一条斜线上。
用回溯法解n后问题，用完全n叉树表示解空间。可行性约束Place剪去不
满足行，列和斜线约束的子树。
下面的解n后问题的回溯法中，递归函数Backtrack(1)实现对整个解空间的
回溯搜索。Backtrack(i)搜索解空间中第i层子树。类Queen的数据成员记录解
空间中节点信息，以减少传给Backtrack的参数。sum记录当前已找到的可行方
案数。
在算法Backtrack中，当i>n是，算法搜索至叶节点，得到一个新的n皇后
互不攻击放置方案，当前已找到的可行方案数sum增1。
当i<=n时，当前扩展节点Z是解空间中的内部节点。该节点有x[i]=1,2,..,n
共n个儿子节点。对当前扩展节点Z的每一个儿子节点，由Place检查其可行
性，并以深度优先的方式递归对可行子树搜索，或剪去不可行子树。
c.算法效率：O(n！)
d.代码:
#include"iostream"
#include"cmath"
using namespace std;
int count=0;
int queenplace[92][8];
int board[8][8];
void putqueen(int ith)
{
int i,k,r;
if(ith==8)
{
count++;
return;
}
for(i=0;i<8;i++)
{
if(board[ith][i]==-1)
{
board[ith][i]=ith;
for(k=count;k<92;k++)
queenplace[k][ith]=i+1;//ithqueeen
//设置控制区域
for(k=0;k<8;k++)
for(r=0;r<8;r++)
if(board[k][r]==-1&&(k==ith || r==i || abs(k-ith)==abs(r-i)))
board[k][r]=ith;
putqueen(ith+1);
//回溯
for(k=0;k<8;k++)
for(r=0;r<8;r++)
if(board[k][r]==ith)
board[k][r]=-1;
}
}
}
int main()
{
int n,i,j;
for(i=0;i<8;i++)
for(j=0;j<92;j++)
queenplace[i][j]=0;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
board[i][j]=-1;
putqueen(0);
cin>>n;
while(n--)
{
int in;
cin>>in;
for(j=0;j<8;j++)
cout< cout< } return 0; } 实验心得（收获、体会） 回溯法有“通用解题法”之称。用它可以系统地搜索一个问题的所有解或任一 解。回溯法在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。 算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定 不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则， 进入该子树，继续按深度优先策略搜索。它适合于解组合数较大的问题
版权声明：本文标题：回溯法实现8皇后问题 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dongtai/1714551871a410733.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论