n后问题
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
n后问题
学号:080710303 姓名:高红霞 一 题目描述
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
二 算法设计分析
用n元组x[1:n]
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示n后问题的解。其中，x[i]表示皇后i放在棋盘的第i行的第x[i]列。由于不允许将2个皇后放在同一列上，所以解向量中的x[i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。将棋盘n*n格看成二维方阵，其行号从上到下，列号从左到右依次编号1，2，…，n。若2个皇后放置的位置分别是(i,j)和(k,j),只要|i-k|=|j-l|成立，就表明2个皇后位于同一斜线上。将隐约束变为显约束。
当我们用回溯法解此题时，想到以下几点:
1初始状态:空棋盘，从第一行开始放置皇后
2目标状态:逐行枚举皇后的位置，最终在n*n棋盘上，摆n个皇后
3边界条件:在n皇后中，即所要枚举皇后位置的行数大于n
4 状态参数:在n皇后问题中，逐行枚举，因此用行指标来作参数
5搜索范围:如何设定for语句中循环变量的初值和终值。n皇后中，对于每一行来说，
1到n列都是可以搜索的范围
6约束条件:n皇后中，以皇后不能在同一行、列、左右对角线为约束条 三 算法的实现-代码
#include
#include
class Queen{
friend int nQueen(int);
private:
bool Place(int k);
void Backtrack(int t);
int n, //皇后个数
*x; //当前解
long sum; //当前已找到的可行
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
数 };
bool Queen::Place(int k) {
for(int j=1;jn) sum++;
else
for(int i=1;i<=n;i++)
{
x[t]=i;
if(Place(t)) Backtrack(t+1);
}
}
int nQueen(int n)
{
Queen X;
//初始化 X
X.n=n;
X.sum=0;
int *p=new int[n+1];
for(int i=0;i<=n;i++)
p[i]=0;
X.x=p;
X.Backtrack(1);
delete []p;
return X.sum;
}
void main(void)
{
int n;
cout<<"请输入皇后的个数";
cin>>n;
cout<<"可行方案数是:"<
本文档为【n后问题分析】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483