作业帮八皇后问题是什么问题呀
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/05/27 00:46:16
八皇后问题是什么问题呀
这就是著名的八皇后问题.八个皇后在排列时不能同在一行、一列或一条斜
线上.在8!=40320种排列中共有92种解决方案.
“八皇后”动态图形的实现
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题.该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法.
高斯认为有76种方案.1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出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!=40320种排列中共有92种解决方案.
“八皇后”动态图形的实现
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题.该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法.
高斯认为有76种方案.1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出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