linux大作业八皇后问题

22013—2014 学年第一学期物电学院期末考试卷。

linux操作系统》

学号姓名班级。

成绩：评语：

考试题目及要求）

八皇后问题。

1、设计背景。

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是国际西洋棋棋手马克斯·贝瑟尔于2023年提出：在8x8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯认为有76种方案。2023年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。

八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于2023年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在2023年由弗朗兹·诺克给出的。

诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。2023年，s.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被格莱舍加以改进。

艾兹格·迪杰斯特拉在2023年用这个问题为例来说明他所谓结构性编程的能力。

算法介绍八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。

二、程序设计的基本思想，原理和算法描述。

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

八皇后问题动态图形的实现，主要应解决以下两个问题。

回溯算法。为解决这个问题，我们把棋盘的横坐标定为i，纵坐标定为j,i和j的取值范围是从1到8。当某个皇后占了位置(i,j)时，在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。

程序说明：(我的linux系统是安装虚拟机上的所以我只有通过截图来说明。)

分为三个部分：具体说明如下：

*主程序*/

#include <>

#include<>

#include”

static char queen[8][8];

static int a[8];

static int b[15];

static int c[15];

int main(int argc,**gr**)

int iline,icolumn; /棋盘初始化，空格为*，放置皇后的地方为@

for(iline=0;iline<8;iline++)

//主、从对角线标记初始化，表示没有冲突。

for(iline=0;iline<15;iline++)

b[iline]=c[iline]=0;

qu(0);

system("pause");

return 0

在桌面终端中vi 开。

*qu.回溯法放置queens*/

#include”

#include<>

static char queen[8][8];

static int a[8];

static int b[15];

static int c[15];

static int iqueennum=0；//记录总的棋盘状态数。

void qu(int i)

int icolumn;

for(icolumn=0;icolumn<8;icolumn++)

在桌面终端中用vi 打开。

#ifndef _qu_h

#define _qu_h

void qu(int i);

#endif

再写一个makefile文件用于同一的编译：

*makefile*/

main：

gcc -o main

gcc -c

经过make统一编译之后得到执行文件main。然后再运行main（即。/main）即可得到如下所示（这里只列举部分运行结果）；

这是我在桌面终端中运行的部分结果。

最后所有生成的文件有如下截图所示：

包括有：main、文件。

三、设计过程：

1. 设计思路及流程：在这次的设计过程中用到了很多的linux的命令并且也熟悉部分语句的用法。

一开始我是在我的电脑上装了一个虚拟机让后再虚拟机上配置了linux系统（red hat linux）。之后在我的虚拟机上做的练习跟作业。

进入虚拟机界面启动rad hat linux 系统。进入根目录下开始作业具体步骤如下：（”n”表示回车）

cd/home

mkdir dazuoye

vi 进入编辑界面输入：

*主程序*/

#include <>

#include<>

#include”

static char queen[8][8];

static int a[8];

static int b[15];

static int c[15];

int main(int argc,**gr**)

int iline,icolumn;

for(iline=0;iline<8;iline++)

for(iline=0;iline<15;iline++)

b[iline]=c[iline]=0;

qu(0);

system("pause");

return 0

保存退出（esc :wq）

vi 进入的编辑界面输入：

#include”

#include<>

static char queen[8][8];

static int a[8];

static int b[15];

static int c[15];

static int iqueennum=0；

void qu(int i)

int icolumn;

for(icolumn=0;icolumn<8;icolumn++)

保存退出后继续编写：vi

#ifndef _qu_h

#define _qu_h

linux大作业八皇后问题

Linux大作业

Linux大作业

Linux大作业

其他用户还读了

linux大作业 八皇后问题

Linux大作业

Linux大作业

Linux大作业

其他用户还读了

linux大作业八皇后问题