辽 宁 科 技 大 学
课程设计说明书
设计题目： 学院、系：专业班级：学生姓名：指导教师: 成 绩： N皇后可视化
九宫格
年 月 日
目录
一、课程设计目的和要求 ............................................ 3 二.题目 ........................................................................... 3 1.N皇后可视化实现 ................................................. 3 2.重排N*N宫游戏 ................................................... 3 三.算法思想描述 ........................................................... 3 1N皇后总体思想为回溯法。 .................................. 3 2九宫图主要用搜索算法A* ................................... 3 四.部分算法代码 ........................................................... 4 1N皇后 ..................................................................... 4 2九宫格 .................................................................... 8 六.测试结果 ................................................................. 10 1N皇后 ................................................................... 10 2九宫格 .................................................................. 11 七.总结 ......................................................................... 12
一、课程设计目的和要求
算法设计与分析是计算机相关专业本科生必须掌握的基本技能，为了进一步加强学生算法设计能力的培养，特开展课程设计环节，以此来强化学生算法的综合利用和设计能力。
要求学生必须认真研究题目要求，自行设计合理的算法。除了统一安排的时间外，学生课下要根据自己的实际情况合理的添加设计时间。
所有的题目要求学生设计合理的核心算法，并给结合可视化开发工具设计出可视化界面。
二.题目
1.N皇后可视化实现
在NxN格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于
同一行、同一列或同一斜线上，问有多少种？
要求：用户输入N值，系统将显示N皇后的实现过程。
2.重排N*N宫游戏
本题目是古代九宫图的推广。原始的九宫问题是：将数字1～8按照任意次序排在3*3的方格阵列中，留下一个空格，与空格相邻的数字可以上下左右移动到空格中。游戏的目标是通过合法的移动，将数字1～8重新排好序。如图：
1 2 3 1 2 3 4 5 4 5 6 6 7 8 7 8 图3 原始图 图4目标状态
一般情况是重排N*N宫问题就是将数字1～N*N-1按照任意的次序排在N*N的方格阵列中，留下一个空格。允许与空格相邻的数字从上下左右4个方向移动到空格中。游戏最终目标是通过合法的移动，将初始状态变换到目标状态。
要求最好用优先队列式分支限界法编程将初始排列通过合法的移动变换为目标状态，并要求移动的次数最少。请给出合法的移动，并给出可视化界面。
三.算法思想描述
1N皇后总体思想为回溯法。
求解过程从空配置开始。在第1列~的m列为合理配置的基础上，再配置第m+1列，直至第n列也是合理时，就找到了一个解。在每列上，顺次从第一行到第n行配置，当第n行也找不到一个合理的配置时，就要回溯，去改变前一列的配置。由于任何两个皇后不能在同一对角线上，可以用 c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j]条件来检测新放入的皇后位置是否合理。 2九宫图主要用搜索算法A*
用于度量节点的“希望”的量度f(n)，即用来衡量到达目标节点的路径的可能性大小。
A*算法：
基本思想：定义一个评价函数，对当前的搜索状态进行评估，找出一个最有希望的节点进行扩展：f(n) = g(n) + h(n)，n为被评价节点
g*(n)：从s到n的最优路径的实际代价 h*(n)：从n到g的最优路径的实际代价
f*(n)=g*(n)+h*(n)：从s经过n到g的最优路径的实际代价 g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值
g (n)通常为从S到到n这段路径的实际代价，则有g (n) ≥ g*(n) h (n):是从节点n到目标节点Sg的最优路径的估计代价. 它的选择依赖于有关问题领域的启发信息，叫做启发函数
A算法：在图搜索的一般算法中，在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序表中的节点进行排序, 找出一个最有希望的节点作为下一次扩展的节点。
在A算法中，如果满足条件：h(n)≤h*(n)，则A算法称为A*算法。 在本算法中，为实现八数码的搜索问题，定义估价函数为：f(n)=g(n)+h(n)， 其中g（n）表示节点n在搜索树中的深度；
h（n）表示节点n的各个数码到目标位置的曼哈顿距离和。
1、算法实现的步骤：
（1）把初始节点S0放入Open表中，置S0的代价g(S0)=0； （2）如果Open表为空，则问题无解，失败退出；
（3）把 Open表的第一个节点取出放入 Closed表，并记该节点为n （4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出； （5）若节点n不可扩展，则转第（2）步；
（6）扩展节点 n，生成其子节点 ni, （其中i=1,2,3,„„），将这些子节点放入 Open表中，并为每一个子节点设置指向父节点的指针；按公式 g（ni）=g(n)＋c(n，ni)（i=1，2，„）计算Open表中的各子节点的代价，并根据各节点的代价对Open表中的全部节点按照从小到大顺序重新进行排序；然后转第（2）步。 2、思路
通过代价函数对Open表中的节点进行排序，代价小的先扩展。
四.部分算法代码 1N皇后
CNqueenView::CNqueenView() { // TODO: add construction code here
Info.t=1; Info.xy=1; int *p=new int [Info.n+1]; for(int i=0;i<=Info.n;i++) p[i]=0; Info.x=p; Info.flg=true; isdraw=0; m_pDC=new CDC; m_pBmp=new CBitmap; }
void CNqueenView::OnDraw(CDC* pDC) { CNqueenDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); // TODO: add draw code for native data here // pDC->SelectObject(m_pBmp); CPen pen; pen.CreatePen(PS_SOLID,2,RGB(255,0,0)); pDC->SelectObject(&pen); CRect rect1(20,20,420,420); pDC->Rectangle(rect1);
if(isdraw) { int k=400/Info.n; for(int i=1;i<=Info.n-1;i++) { pDC->MoveTo(20+i*k,420); pDC->LineTo(20+i*k,20); } for(int j=1;j<=Info.n-1;j++) { pDC->MoveTo(420,20+j*k); pDC->LineTo(20,20+j*k); } CPen pen1; pen1.CreatePen(PS_SOLID,2,RGB(255,0,0)); pDC->SelectObject(&pen1); CRect rect2(25+(Info.t-1)*k,25+(Info.xy-1)*k,15+Info.t*k,15+Info.xy*k); pDC->Ellipse(rect2);
}
void CNqueenView::OnInputdata() { // TODO: Add your command handler code here Dlg dlg; if(dlg.DoModal()==IDOK) { Info.n=dlg.m_n; isdraw=1; Invalidate(); SetTimer(1,450, NULL); pThread=AfxBeginThread(tr,&Info); } }
void Backtrack(int tx) { Info.hthread=GetCurrentThread();
if(tx>Info.n) { // sum++; AfxMessageBox(\"结束\"); AfxMessageBox(\"总共有sum\"); // return; } else for(int i=1;i<=Info.n;i++) { Info.xy=i; Info.x[tx]=i; Info.t=tx; Sleep(500); // OnDraw(pDC);
// CRect rect3(25+(t-1)*k,25,15+(t)*k,15+4*k); // InvalidateRect(rect3); if(Place(tx)) {
Backtrack(tx+1); } } }
bool Place(int t) {
// CNqueenView info; for(int j=1;jvoid search(int cur) {int i,j;
if(cur==n) { cout<else for(i=0;iok=0;break; } if(ok) search(cur+1); } }void main() {
cout<<\"请输入皇后的个数n:\"; cin >>n;
//for(i=0;isearch(0); cout<cout<<\" 总共有 \"<2九宫格A*算法代码的核心部分
pnode move(pnode p,int dir) {
pnode Unode=(pnode)malloc(sizeof(node)); for(int i=0;i<=2;i++) { for(int j=0;j<=2;j++) {
Unode->a[i][j]=p->a[i][j]; } }
switch(dir) {
case 1: //up {
Unode->x=p->x-1; Unode->y=p->y;
Unode->a[Unode->x][Unode->y]=0;
Unode->a[Unode->x+1][Unode->y]=p->a[Unode->x][Unode->y]; break; }
case 2:………………//down }
Unode->father=p;
Unode->g=p->g+1;//深度增加一层
Unode->h=hvalue(Unode->a,final); //更新h函数值 Unode->f=Unode->h+Unode->g; return Unode;
}
int main(int argc, char *argv[]) {
pnode A0=(pnode)malloc(sizeof(node)); pnode open, //open表头 close, //close表头 now, //当前节点
Lnode,Rnode,Unode,Dnode, //下一个左，右，上，下节点 fnode; //终节点 initial(A0,start); open=A0; close=NULL; while(1) {
if(open==NULL) //Open表为空，未找到解，结束搜索程序 {
fnode=NULL;
cout<<\"未能找到解\" ; return 0; }
if(open->h==0) //open表中第一个节点是解，结束搜索 {
fnode=open; //把final node从open表中拿出，放到close表中 open=open->next; fnode->next=NULL; fnode->clnext=close; close=fnode; break; }
now=open; int X,Y;
X=now->x;Y=now->y;
if((X>0)&&(now->father==NULL||now->father->x!=X-1)) {
Unode=move(now,1); //空格上移，得到新节点 insert(Unode,open); //把新节点插入open表中 }
if((X<2)&&(now->father==NULL||now->father->x!=X+1)) { //空格下移 Dnode=move(now,2); insert(Dnode,open); }
if((Y>0)&&(now->father==NULL||now->father->y!=Y-1))
{
Lnode=move(now,3); insert(Lnode,open); }
if((Y<2)&&(now->father==NULL||now->father->y!=Y+1)) {
Rnode=move(now,4); insert(Rnode,open); }
now->clnext=close; //把当前节点放入到close表 close=now;
open=open->next; //把open表头指向下一个表内节点 }
while(fnode->father!=NULL) //回溯到始节点，建立解的链表 {
fnode->father->next=fnode; fnode=fnode->father; }
while(fnode!=NULL) //从头节点打印到终节点 {
disp(fnode);
fnode=fnode->next; }
freeclose(close); //释放close表中节点的内存 freeopen(open); //释放open表中节点的内存 return 0;
}
六.测试结果 1N皇后
2九宫格
七.总结
自从学习编程起，就开始接触算法，而对于MFC可视化编程则是很少接触，除了大一时做过一些简单的控件之外 就没看过了。对于这次课程设计来说，可视化设计是个难题。从图书馆借了相关方面的书来参考，不过MFC也不是短时间就能学会的，于是还是参考别人的作品。不过自己也还是学会了MFC的一些类和函数.。而对于九宫格的A*算法我也是看了很久，感觉自己的要学的还是很多的，虽然自己的做的不好，但是却给了我很大的动力同时也激发了自己对软件设计的兴趣。自己做不出来是因为自己没自学这些知识，我以后要多学些知识，把理论知识应用于实践，增强自己的动手能力。看到自己即将毕业，才发现再就业之前要学的专业知识还是很多的。
在此期间我们失落过，也曾一度热情高涨。从开始时满富盛激情到最后汗水背后的复杂心情，点点滴滴无不令我回味无长。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和思考的能力。
