问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

八皇后问题

发布网友 发布时间:2022-04-10 23:30

我来回答

1个回答

热心网友 时间:2022-04-11 00:59

八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。事实上就是有92种解法。

对于八皇后问题的实现,如果结合动态的图形演示,则可以使算法的描述更形象、更生动,使教学能产生良好的效果。下面是笔者用Turbo C实现的八皇后问题的图形程序,能够演示全部的92组解。八皇后问题动态图形的实现,主要应解决以下两个问题。

1.回溯算法的实现
(1)为解决这个问题,我们把棋盘的横坐标定为i,纵坐标定为j,i和j的取值范围是从1到8。当某个皇后占了位置(i,j)时,在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。用语句实现,可定义如下三个整型数组:a[8],b[15],c[24]。其中:

a[j-1]=1 第j列上无皇后
a[j-1]=0 第j列上有皇后
b[i+j-2]=1 (i,j)的对角线(左上至右下)无皇后
b[i+j-2]=0 (i,j)的对角线(左上至右下)有皇后
c[i-j+7]=1 (i,j)的对角线(右上至左下)无皇后
c[i-j+7]=0 (i,j)的对角线(右上至左下)有皇后

(2)为第i个皇后选择位置的算法如下:

for(j=1;j<=8;j++) /*第i个皇后在第j行*/
if ((i,j)位置为空)) /*即相应的三个数组的对应元素值为1*/
{占用位置(i,j) /*置相应的三个数组对应的元素值为0*/
if i<8
为i+1个皇后选择合适的位置;
else 输出一个解
}

2.图形存取
在Turbo C语言中,图形的存取可用如下标准函数实现:

size=imagesize(x1,y1,x2,y2) ;返回存储区域所需字节数。
arrow=malloc(size);建立指定大小的动态区域位图,并设定一指针arrow。
getimage(x1,y1,x2,y2,arrow);将指定区域位图存于一缓冲区。
putimage(x,y,arrow,copy)将位图置于屏幕上以(x,y)左上角的区域。

3. 程序清单如下

#i nclude <graphics.h>
#i nclude <stdlib.h>
#i nclude <stdio.h>
#i nclude <dos.h>
char n[3]={0,0};/*用于记录第几组解*/
int a[8],b[15],c[24],i;
int h[8]={127,177,227,277,327,377,427,477};/*每个皇后的行坐标*/
int l[8]={252,217,182,147,112,77,42,7};/*每个皇后的列坐标*/
void *arrow;
void try(int i)
{int j;
for (j=1;j<=8;j++)
if (a[j-1]+b[i+j-2]+c[i-j+7]==3) /*如果第i列第j行为空*/
{a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*占用第i列第j行*/
putimage(h[i-1],l[j-1],arrow,COPY_PUT);/*显示皇后图形*/
delay(500);/*延时*/
if(i<8) try(i+1);
else /*输出一组解*/
{n[1]++;if (n[1]>9) {n[0]++;n[1]=0;}
bar(260,300,390,340);/*显示第n组解*/
outtextxy(275,300,n);
delay(3000);
}
a[j-1]=1;b[i+j-2]=1;c[i-j+7]=1;
putimage(h[i-1],l[j-1],arrow,XOR_PUT);/*消去皇后,继续寻找下一组解*/
delay(500);
}
}
int main(void)
{int gdrive=DETECT,gmode,errorcode;
unsigned int size;
initgraph(&gdrive,&gmode,"");
errorcode=graphresult();
if (errorcode!=grOk)
{printf("Graphics error\n");exit(1);}
rectangle(50,5,100,40);
rectangle(60,25,90,33);
/*画皇冠*/
line(60,28,90,28);line(60,25,55,15);
line(55,15,68,25);line(68,25,68,10);
line(68,10,75,25);line(75,25,82,10);
line(82,10,82,25);line(82,25,95,15);
line(95,15,90,25);
size=imagesize(52,7,98,38); arrow=malloc(size);
getimage(52,7,98,38,arrow);/*把皇冠保存到缓冲区*/
clearviewport();
settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4);
setusercharsize(3, 1, 1, 1);
setfillstyle(1,4);
for (i=0;i<=7;i++) a[i]=1;
for (i=0;i<=14;i++) b[i]=1;
for (i=0;i<=23;i++) c[i]=1;
for (i=0;i<=8;i++) line(125,i*35+5,525,i*35+5);/*画棋盘*/
for (i=0;i<=8;i++) line(125+i*50,5,125+i*50,285);
try(1);/*调用递归函数*/
delay(3000);
closegraph();
free(arrow);
}

八皇后问题的串行算法

1 八皇后问题

所谓八皇后问题,是在8*8格的棋盘上,放置8个皇后。要求每行每列放一个皇后,而且每一条对角线和每一条反对角线上不能有多于1个皇后,也即对同时放置在棋盘的两个皇后(row1,column1)和(row2,column2),不允许(column1-column2)=(row1-row2)或者(column1+row1)=(column2+row2)的情况出现。

2 八皇后问题的串行递归算法

八皇后问题最简单的串行解法为如下的递归算法:

(2.1)深度递归函数:

go(int step,int column)

{int i,j,place;

row[step]=column;

if (step==8)

outputresult( ); /*结束递归打印结果*/

else /*继续递归*/

{for(place=1;place<=8;place++)

{for(j=1;j<=step;j++)

if(collision(j ,row[j],step+1,place))

/*判断是否有列冲突、对角线或反对角线*/

goto skip_this_place;

go(step+1,place);

skip_this_place:;

}

}

}/* go */

(2.2)主函数:

void main( )

{int place,j;

for(place=1;place<=8;place++)

go(1,place);

}/* main */

八皇后问题的并行算法

该算法是将八皇后所有可能的解放在相应的棋盘上,主进程负责生成初始化的棋盘,并将该棋盘发送到某个空闲的子进程,由该子进程求出该棋盘上满足初始化条件的所有的解。这里,我们假定主进程只初始化棋盘的前两列,即在棋盘的前两列分别放上2个皇后,这样就可以产生8*8=64个棋盘。

1 主进程算法

主进程等待所有的子进程,每当一个子进程空闲的时侯,就向主进程发送一个Ready(就绪)信号。主进程收到子进程的Ready信号后,就向该子进程发送一个棋盘。当主进程生成了所有的棋盘后,等待所有的子进程完成它们的工作。然后向每个子进程发送一个Finished信号,打印出各个子进程找到的解的总和,并退出。子进程接收到Finished信号也退出。

2 子进程算法

每个子进程在收到主进程发送过来的棋盘后,对该棋盘进行检查。若不合法,则放弃该棋盘。子进程回到空闲状态,然后向主进程发送Ready信号,申请新的棋盘;若合法,则调用move_to_right(board,rowi,colj)寻找在该棋盘上剩下的6个皇后可以摆放的所有位置,move_to_right(board,rowi,colj)是个递归过程, 验证是否能在colj列rowi行以后的位置是否能放一个皇后。

1)首先将more_queen设置成FALSE;

以LEAF,TRUE和FLASE区分以下三种情况:

A)LEAF:成功放置但是已到边缘,colj现在已经比列的最大值大1,回退两列,检查是否能将待检查皇后放在哪一行:如果能,把more_queen设成TRUE;

B)TRUE:成功放置皇后,检查这一列是否能有放置皇后的其他方式,如有,把more_queen设成TRUE;

C)FALSE:不能放置,回退一列再试,如果能把more_queen设成TRUE ,如果皇后已在最后一行,必须再检查上一列。

2)如果more_queens=TRUE,仍需再次调用move_to_right(),为新棋盘分配空间,用xfer()将现有棋盘拷贝到nextboard,并进行下列情况的处理:

TRUE:得到一个皇后的位置,增大列数再试;

FALSE:失败,如果more_queen为真, 取回棋盘,保存上次调用的棋盘。将列数减小,取走皇后,增加行数,再调用move_to_right();

LEAF:得到一种解法,solution增一,将解法写入log_file,由于已到边缘,列数回退1,检查是否放置一个皇后,如果能,新加一个皇后后,调用move_to_right;如果不能,检查more_queen如果more_queen为真,将棋盘恢复到上次调用时保存的棋盘,将待检查的皇后下移,调用move_to_right。

八皇后问题的高效解法-递归版

// Yifi 2003 have fun! : )

//8 Queen 递归算法
//如果有一个Q 为 chess[i]=j;
//则不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置

class Queen8{

static final int QueenMax = 8;
static int oktimes = 0;
static int chess[] = new int[QueenMax];//每一个Queen的放置位置

public static void main(String args[]){
for (int i=0;i<QueenMax;i++)chess[i]=-1;
placequeen(0);
System.out.println("\n\n\n八皇后共有"+oktimes+"个解法 made by yifi 2003");
}

public static void placequeen(int num){ //num 为现在要放置的行数
int i=0;
boolean qsave[] = new boolean[QueenMax];
for(;i<QueenMax;i++) qsave[i]=true;

//下面先把安全位数组完成
i=0;//i 是现在要检查的数组值
while (i<num){
qsave[chess[i]]=false;
int k=num-i;
if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false;
if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false;
i++;
}
//下面历遍安全位
for(i=0;i<QueenMax;i++){
if (qsave[i]==false)continue;
if (num<QueenMax-1){
chess[num]=i;
placequeen(num+1);
}
else{ //num is last one
chess[num]=i;
oktimes++;
System.out.println("这是第"+oktimes+"个解法 如下:");
System.out.println("第n行: 1 2 3 4 5 6 7 8");

for (i=0;i<QueenMax;i++){
String row="第"+(i+1)+"行: ";
if (chess[i]==0);
else
for(int j=0;j<chess[i];j++) row+="--";
row+="++";
int j = chess[i];
while(j<QueenMax-1){row+="--";j++;}
System.out.println(row);
}
}
}
//历遍完成就停止
声明声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。E-MAIL:11247931@qq.com
纽约唐人街碎尸案的电影剧情 成年人可以喝金银花益生菌吗 金银花益生菌基本信息 金银花益生菌简要说明 益生瑞氢氧康养机价格 有哪些嗜好是女性怀孕后必须戒掉的?为什么呢? 玻璃为什么有无铅玻璃 pb 什么概念 智能密码锁找哪家更省钱? ...挑选一下那个比较有意思?姓郑。梓昸.梓瞳.炜东.炜桐.炜楠.炜森... 温州龙湾开发区英诺华电子有限公司拖欠工资,15年l月份工资还没发。多次索要无果,我向龙湾劳动局求助 北京业之峰诺华装饰有做阿米巴么? 阿斯利康,辉瑞,诺华哪个好?现在在辉瑞实习呢,同时拿到了阿斯利康和诺华的OFFER,现在不知道做什么选择 有没有人做过诺华期指被骗的? 阿斯利康和诺华哪个好 谁知道成都业之峰诺华报价怎么样?为什么成都装修公司报价差别那么大 我想进辉瑞、强生、诺华、葛兰素史克等制药企业 你好,请问你做完人格测试后成功入职诺华了吗?是否这个测试已代表整个面试成功了80%? 进制药公司对本科,研究生专业的要求,有经验回答 最好是拜耳,诺华的 诺华制药做背景调查会调查学历吗 诺华公司面试应注意哪些问题? 诺华面试 诺华面过了大区经理,收到了人力的电话,让做人格测试,请高人指点有希望吗? 诺华的(Senior) MSL和一家股份制医院的医生,我该怎么选择? 宝马拿铁是顶杆发动机吗 宝马摩卡壶选择哪种比较好 宝马拿铁适合身高多少 宝马拿铁是什么挡? 宝马拿铁几个档位? 宝马拿铁三个版本有什么区别? 宝马拿铁和r18怎么选 京东金条怎么开通?先要开通京东金条首 怎么把网盘下载的壁纸保存到手机 如果我冲着精灵宝可梦日月而买的3ds,那我要不要破不破解? 商家的回答很模糊,我不是很懂。求大神解 精灵宝可梦日月 盗版和正版有什么区别 我的世界版精灵宝可梦水跃鱼在哪抓 如何在我的世界精灵宝可梦模组里召唤出二宙斯 妈妈说想要买一个手镯,是翡翠的好还是还和田玉的好? 怀孕血糖高可以吃的水果有哪些 孕期血糖高可以吃什么水果蔬菜 怀孕血糖高可以吃什么水果 怀孕七个月了血糖高可以吃什么水果 怀孕初期,检查显示血糖数值有点偏高了,不知道吃什么水果好呢? 怀孕中期血糖高可以吃什么水果 注册免费 怎么免费申请一个? 我想申请一个怎么申请的 申请一个新的需要什么条件? 申请一个新的需要什么条件? 免费申请一个 注册免费立即申请