试验程序：
//八??皇¨o后¨?问¨o题?a
int icount=0,Queens[8];
void Output()
{
int flag=1;
cout<<"the "<<++icount<<" way to place 8 queens is:"< cout<<" ---------"< for(int i=0;i<8;i++) { cout<<" |"; for(int j=0;j<8;j++) { if(Queens[i]-1==j) cout<<"*"; else if(flag<0) cout<<" "; else cout<<"o"; flag=-1*flag; } cout<<"|"< flag=-1*flag; } cout<<" ---------"< } int Isvalid(int n) { for(int i=0;i { if(Queens[i]==Queens[n]) return 0; if(abs(Queens[i]-Queens[n])==(n-i)) return 0; } return 1; } void Queen(int n) { if(n==8) { Output(); return; } for(int i=1;i<=8;i++) { Queens[n]=i; if(Isvalid(n)) { Queen(n+1); } } } 主函数调用为： int main（） { Queen(0); return 0; } 实验结果： 深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：15级软工学术型实验时间：2015-12-08 实验报告提交时间：2015-12-09 教务部制 一．实验目的 1.掌握选回溯法设计思想。 2.掌握八皇后问题的回溯法解法。 二．实验步骤与结果 实验总体思路： 根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。 回溯法的实现及实验结果： 1、判断函数 代码1： procedure BTrack_Queen(n) //如果一个皇后能放在第K行和X(k)列，则返回true，否则返回false。 global X(1:k);integer i,k i←1 while i 流程图 八皇后问题算法分析 在这个问题中首先定义的是一个用于构造界面的二位数组a【i】【j】和一个用于判断的表头数组number【】。在开始进行八皇后棋子排列的时候，首先对行进行递增循环，即i初始值为0，每次i++，i最大值为8的循环。在每次循环中产生一个小于8的随机数q，然后判断表头数组number【】中number【q】位置的值是否为1，如果不是，则在二维数组a【i】【q】位置上打印表示棋子的“K”；如果为1，则返回产生随机数的步骤继续产生随机数。在循环到i>8时，跳出循环，这时候一个完整的八皇后排列也就出来了。 源代码： package queen; import java.awt.*; import java.awt.event.*; class equeen extends Frame implements ActionListener{ //构造界面和定义数组 Button enter; Button clean; Button exit; int number[] = new int[8]; int i,j,q; Label a[][] = new Label[8][8]; equeen(String s){ GridLayout grid; grid = new GridLayout(9,8); setLayout(grid); enter = new Button("begin"); clean = new Button("clean"); exit = new Button("esit"); for(int i = 0;i<8;i++){ for(int j = 0;j<8;j++){ a[i][j] = new Label(); if((i+j)%2==0)a[i][j].setBackground(Color.yellow); else a[i][j].setBackground(Color.gray); add(a[i][j]); } } for(int i = 0;i<8;i++){ number[i] = 0;//初始化判断数组 } add(enter); add(clean); add(exit); enter.addActionListener(this); clean.addActionListener(this); exit.addActionListener(this); setBounds(100,100,300,300); setVisible(true); validate(); } public void actionPerformed(ActionEvent e){ if(e.getSource()==enter){ for(int i =0;i<8;i++){ for(int j=0;j<8;j++){ a[i][j].setText(""); } } for(int i =0;i<8;i++){ while(true){ q = (int)(Math.random()*8); if(number[q]==0){ a[i][q].setText("K"); number[q] = 1; break; } else if(number[q]!=0) continue; } } for(int i = 0;i<8;i++){ number[i] = 0; } } 工学院 数据结构课程设计报告设计题目：八皇后 2008 年 6 月25 日 设计任务书 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法 目录 1. 课题综述 (1) 1.1课题的来源及意义 (1) 1.2面对的问题 (1) 2. 需求分析 (1) 2.1涉及到的知识 (2) 2.2软硬件的需求 (2) 2.3功能需求 (2) 3. 概要设计 (2) 4. 详细设计和实现 (3) 4.1算法描述及详细流程图 (3) 4.1.1算法描述 (3) 4.1.2算法流程图 (3) 5. 代码编写及详细注释 (4) 6. 程序调试 (8) 6.1调试过程、步骤及遇到的问题 (8) 7. 运行与测试 (8) 7.1运行演示 (8) 总结 (10) 致 (11) 参考文献 (12) . 1. 课题综述 1. 1课题的来源及意义 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。 到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。 1. 2 面对的问题 1）解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； 2）使用数据结构的知识，用递归法解决问题。 2. 需求分析 八皇后问题 问题描述： 在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相冲突 （在每一横列，竖列，斜列只有一个皇后）。 求解： 标题: 八皇后问题的解（回溯法程序代码） 发信站: 网易虚拟社区(Fri Jul 14 10:06:52 2000),站内信件 以前上学的时候，写8皇后程序的时候偷懒用最笨的算法，在8086上计算十皇后的时候，我放了张纸条，说明计算机正在运行，然后去吃饭，吃完以后，才看到结果。前几天，刚好有空，所以重写了一次，以补当年的遗憾。 #include "stdio.h" int attacked(int *array,int position){ int flag=-1; float step; if(position==1) return flag; for(step= 1.00;step (array+(int)step)-*(array+position))/(step-position))==-1){ flag=1; break;}} return flag;}void main(void){ int countSum,queenSum,printCount,*queenArray,queenPosition=0; int tempArray[20]={66,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; countSum=1; queenArray=tempArray; printf("input you queenSum here: "); scanf("%d",&queenSum); fflush(stdin); if(queenSum<4){ printf("the %d queen's sum is 0\n",queenSum); return;}for(;;){ if(countSum M文件 function PlaceQueen(row,matrix,N)%回溯法放置皇后 if row>N PrintQueen(N,matrix);%打印棋盘 else for col=1:N matrix(row,col)=1; if row==1||Conflict(row,col,N,matrix)%检测是否冲突 PlaceQueen(row+1,matrix,N); end matrix(row,col)=0; end end %子函数：检测冲突 function result=Conflict(row,col,N,matrix)%检测是否冲突 result=1; for i=1:row-1 for j=1:N if matrix(i,j)==1 if ((j==col)||(abs(row-i)==abs(col-j)))%是否产生冲突：在同一直线，斜线上 result=0; break; end end end if result==0 break; end end %子函数：打印棋盘信息 function PrintQueen(N,matrix) global solutionNum; %定义全局变量，来累积方法数 solutionNum=solutionNum+1; disp(['第',num2str(solutionNum),'种方法：']) disp(matrix) 脚本文件 clear all clc global solutionNum; solutionNum=0;%全局变量记录方法数 N=8;%皇后个数 matrix=zeros(N);%存储皇后位置信息 PlaceQueen(1,matrix,N)%调用放置方法 计算机科学与技术专业 数据结构课程设计报告设计题目：八皇后问题 目录 1需求分析 (3) 1.1功能分析 (3) 1.2设计平台 (4) 2概要设计 (4) 2.1算法描述 (5) 2.2算法思想 (6) 2.3数据类型的定义 (6) 3详细设计和实现 (7) 3.1算法流程图 (7) 3.2 主程序 (7) 3.3 回溯算法程序 (8) 4调试与操作说明 (10) 4.1调试情况 (10) 4.2操作说明 (10) 5设计总结 (12) 参考文献 (13) 附录 (13) 1需求分析 1.1功能分析 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有92个解答。 1、本演示程序中，利用选择进行。程序运行后，首先要求用户选择模式，然后进入模式。皇后个数设0 回溯法解八皇后问题 在N * N 格的棋盘上放置彼此不受攻击的N 个皇后。N个皇后问题等价于在N * N 格的棋盘上放置N 个皇后，任何2个皇后不在同一行或同一列或同一斜线上。当N等于8，就是著名的八皇后问题。 此问题是通过C语言程序编写的，在Turboc环境下完成实现的。输出结果见（输出结果。TXT文件） 详细代码为： /*///////////////////////////////////////////////////////////////////// /// /////The programming is a complex problem about the ways of queens./////// /////Programmer: Luo Xiaochun /////// /////Completed date: 2007.12 //////// /////V ersion number: Turboc 2.0 //////// /////////////////////////////////////////////////////////////////////// /*/ #include 八皇后问题（回溯法）2009-08-11 12:03问题描述： 求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局，这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线4个方向互相捕捉。 解题思路： 总体思想为回溯法。 求解过程从空配置开始。在第1列~的m列为合理配置的基础上，再配置第m+1列，直至第n列也是合理时，就找到了一个解。在每列上，顺次从第一行到第n行配置，当第n行也找不到一个合理的配置时，就要回溯，去改变前一列的配置。 为使在检查皇后配置的合理性方面简易方便，引入一下4个工作数组： ?数组col[i],表示在棋盘第i列，col[i]行有一个皇后； ?数组a[],a[k]表示第k行上还没有皇后； ?数组b[],b[k]表示第k列右高左低斜线上没有皇后； ?数组c[],c[k]表示第k列左高右低斜线上没有皇后； 代码： #include 八皇后问题学 2012年 9 月 5 日 目录 一、选题 1.1背景知识 (2) 1.2设计目的与要求 (2) 二、算法设计 2.1问题分析 (3) 2.2算法设计 (3) 三、详细设计 3.1源程序清单 (4) 四、调试结果及分析 4.1调试结果 (6) 4.2调试分析 (7) 五、课程设计总结 5.1总结及体会 (7) 六、答辩 6.1答辩记录 (8) 6.2教师意见 (8) 一、选题及背景知识 1.1 背景知识 在国际象棋中，皇后是一个威力很大的棋子，她可以“横冲直撞”（在正负或垂直方向走任意步数），也可以“斜刺冲杀”（在正负45度方向走任意步数），所以在8*8的棋盘上要布互相不受攻击的皇后，最多只能布八个，共92种布法，再也不能有别的布法了——这就是著名的八皇后问题 在8*8的国际象棋棋盘上，放置八个皇后，使得这八个棋子不能互相被对方吃掉。也就是说一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 1.2 设计要求 要求：·判断在国际象棋中，能否在空棋盘上摆放8个皇后，并使其中任意两个皇后不能在同一行，同一列或同一对角线上。 ·编写完整的摆放八皇后问题的程序 ·具体要求第一个皇后的起始位置由键盘输入 二、算法设计 2.1问题分析 设计——图形表示下图中，Q代表皇后 假设在第k列上找到合适的位置放置一个皇后，要求它与第1——k-1列上的皇后不同行、列、对角线；可以从图上找到规律：不同列时成立，皇后放在第k列上；讨论行时，第j个皇后的位置（a[j] ，j）要与（i，k）位置的皇后不同行；如果同在／斜线上，行列值之和相同；如果同在＼斜线上，行列值之差相同；如果斜线不分方向则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同,可表示为（|a[j]-i|=|j-k|）。 2.2 算法设计 利用计算机运行速度快的特点，采用枚举法，逐一尝试各种摆放方式，来判断最终摆法。其中判断是否同在对角线上用到了：行数差的绝对值与列数差的绝对值相等， 课程设计报告 课程名称数据结构课程设计 课题名称八皇后问题演示 专业通信工程 班级通信工程1081 学号201013120103 姓名刘献文 指导教师田娟秀郭芳 2012年7 月 6 日 湖南工程学院 课程设计任务书 课程名称数据结构 课题八皇后问题演示 专业班级通信工程1081 学生姓名刘献文 学号201013120103 指导老师田娟秀郭芳 审批 任务书下达日期2012 年7 月 1 日 任务完成日期2012 年7 月 6 日 1设计内容与设计要求 1.1设计内容 （4）课题四：八皇后问题演示 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。 设计思路：解决8皇后时，在安放第i行皇后时，需要在列的方向从1到n试 探(j =1,…, n)：首先在第j列安放一个皇后，如果在列、主对角线、次对角线方 向有其它皇后，则出现攻击，撤消在第j列安放的皇后。如果没有出现攻击，在第 j列安放的皇后不动，递归安放第i+1行皇后。 对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动。要求用Turbo C或VC6.0 MFC实现的八皇后问题的图形程序，能够演示全部的92组解。 1.2 选题方案： 所选题目根据学号确定，学号模6加1，即（学号%6+1）。如你的学号为9，则 所选题目号为：9%6+1＝（题目4）。注意，所有的课题都要求用图形方式演示步骤 和结果。同学们可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法。 1.3设计要求： 1.3.1 课程设计报告规范 （1）需求分析 a.程序的功能。 b.输入输出的要求。 （2）概要设计 a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块 的功能。 淮阴工学院 数据结构课程设计报告 设计题目：八皇后 系（院）:计算机工程系 专业：信息安全 班级：信息 1 0 6 学生姓名: 叶青学号:1061303127 指导教师:张亚红寇海洲胡荣林夏森 学年学期: 2007 ~ 2008 学年第 2 学期 2008 年 6 月25 日 设计任务书 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法 目录 1. 课题综述 (1) 1.1课题的来源及意义 (1) 1.2面对的问题 (1) 2. 需求分析 (1) 2.1涉及到的知识 (1) 2.2软硬件的需求 (1) 2.3功能需求 (2) 3. 概要设计 (2) 4. 详细设计和实现 (2) 4.1算法描述及详细流程图 (2) 4.1.1算法描述 (3) 4.1.2算法流程图 (3) 5. 代码编写及详细注释 (4) 6. 程序调试 (7) 6.1调试过程、步骤及遇到的问题 (7) 7. 运行与测试 (7) 7.1运行演示 (7) 总结 (9) 致谢 (10) 参考文献 (11) . 算法设计与分析 实验报告 —八皇后问题 - 姓名：崔明鑫 学号：08208012 班级：软件83 【问题描述】 在国际象棋盘上放八个皇后，要求任一皇后吃不到别人，也不受其他皇后的攻击，求出问题的所有解。 【问题分析&算法设计】 用8元组x[1: n]表示8后问题。其中x[ i]表示皇后i放在棋盘的第i行的第x[ i]列。由于不允许将2个皇后放在一列，所以解向量中的x[ i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。故若2个皇后放置的位置分别是（i，j）和（k，l），且i – j = k – l或i + j = k + l，则说明这2个皇后处于同一斜线上。这两个方程分别等价于i – k = j – l和i – k = l – j。由此可知，只要|i - k| = |j - l|成立，就表明2个皇后位于同一条斜线上。问题的隐约束化成了显约束。用回溯法解决8皇后问题时，用完全8叉树表示解空间。 【算法实现】 #include "stdio.h" #include "math.h" #include "iostream.h" #define N 8 /* 定义棋盘大小*/ static int sum; /* 当前已找到解的个数*/ static int x[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列*/ /* 每找到一个解,打印当前棋盘状态*/ void Show() { sum++; cout << "第" << sum << "种情况：" << endl; cout << "坐标为:\t"; for(int k = 0; k < N; k++) 注意：本文编程使用c++！！！ c语言编程在最后！！！ 目录 一、需求分析 (1) 二、概要设计 (3) 三、详细设计 (5) 四、调试分析及测试 (8) 五、个人工作及创新 (12) 六、小结 (12) 参考文献 (13) 附录 (13) 一、需求分析 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。 所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有92个解答。 1.1 涉及到的知识点 本次课程设计中，用到的主要知识有：递归法、回溯法的应用,for语句的灵活运用，数据结构中树知识的灵活运用、栈及数组的掌握. 下面给出八皇后问题回溯算法的伪代码 PlaceQueen(row) for 第row行的各列col If 位置（row,col）可以放置皇后 在位置（row,col）放置一个皇后 If(row<9) PlaceQueen(row+1); else 成功，打印棋盘 将位置（row,col）上的皇后取走，尝试下一列位置 //回溯 其中回溯法的应用如下： 回溯法也是设计递归过程的一种重要方法，原理或步骤为：试着先把第一个皇后放在棋盘上，然后再放第二个，使两个皇后不会互相攻击，再放第三个皇后，使得她与前面两个皇后都不会互相攻击，依此类推，直至所有的皇后都放上去。如果第七个皇后放上后，第八个皇后已经没有安全的位置可以放置，则试着调试第七个皇后的位置，再尝试第八个皇后有没有安全的位置；如果第七个皇后的所有安全位置都已尝试过了，第八个皇后还是没有安全的位置，则试着调试第六个皇后的位置，重新放置第七、八个皇后的尝试。如此类推，最糟糕的事情就是一直到将第一个皇后的位置进行调整。 1.2 功能要求 当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比 较直观的界面显示。 进入界面后，就会提示输入字符串的输入形式，在八皇后求解程序中， 只要你选择输出解的格式，选择1则显示为每一列皇后的放置的行数，，选 择2则显示的是以矩阵形式形象的显示皇后的放置位置，选择0则退出程序 的调试。在调试结果中，1的位置也就表示了该皇后应该所在的位置，0代表 了空位置。 二、概要设计 2.1 数据结构 1.解数组a，a[i]表示第i个皇后放置的列，范围为1~8。 2. 行冲突标记数组b，b[j]=0 表示第j行空闲，b[j]=1 表示第j行被 占领，范围为1~8。 3. 对角线冲突标记数组c、d。c[i-j]=0 表示第（i-j）条对角线空闲，c[i-j]=1 表示第（i-j）条对角线被占领，范围-7~7。d[i+j]=0 表示第（i+j）条对角线空闲，d[i+j]=1 表示第（i+j）条对角线被占领，范围2~16。 八皇后问题JAVA程序 public class Queen { static int QueenMax = 8; static int times = 0; static int chess[] = new int[QueenMax]; public static void placequeen(int num) { int i=0; boolean save[] = new boolean[QueenMax]; for(;i 算法设计及分析 n皇后问题---回溯求解 国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动；也可以如同 “象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么， 在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢？这个问题是伟 大数学家高斯在十九世纪中期提出来的，并作了部分解答。高斯在棋盘上放下了N个互不攻 击的皇后，他还认为可能有N种不同的放法，这就是有名的“N皇后”问题。如果你动手试试， 就一定会发现开头几颗皇后很容易放置，越到后来就越困难。由于我们的记忆有限，很可能 在某个位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走 弯路，花费大量的精力。因此，必须找到一个简易有效、有条不紊的法则才行。 回溯法的基本思想： 对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的 每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况； 从而得出结果。在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这 也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些不可能的解，这样就不 必继续把解的剩余部分列出从而节省部分时间。 不妨以8皇后为例，设8皇后为x i，她们分别在第i行（i=1,2,3,4,5,6,7,8）,这样问 题的解空间就是一个8个皇后所在列的序号，为n元一维向量（x1,x2,,x3,x4,x5,x6,x7,x8），搜 索空间是1≤x i≤8（i=1,2,3,4,5,6,7,8）,共88个状态。约束条件是8个点 （1,x1）,(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)不在同一列和同一对角线上。虽 然问题共有88个状态，但算法不会真正地搜索这么多的状态，因为回溯法采用的是“走不通 就掉头”的策略，而形如（1,1,x3,x4,x5,x6,x7,x8）的状态共有86个，由于1,2号皇后在同一 列不满足约束条件，回溯后这些状态是不会搜索的。 算法设计： 我们用三个数组c,b,d分别记录棋盘上的n个列，2n-1个住对角线和2n-1个副对角线的 占用情况。用i,j分别表示皇后所在的行列，用表达式i-j+n对主对角线编号，范围是1～2n-1， 用i+j为负对角线编号，范围为2～2n. 程序代码： #include"stdio.h" int a[20],b[20],c[40],d[40],n,i,k; int t=0; //t记录解的个数 void output() { t=t+1; printf("第%d个解:",t); for(k=1;k<=n;k++) printf("%d",a[k]); printf("\n"); } void find(int i) { int j; for(j=1;j<=n;j++) //第i个皇后有n种可能位置 if(b[j]==0&&c[i+j]==0&&d[i-j+n]==0) //判断位置是否冲突 {a[i]=j; //摆放皇后 b[j]=1; //占领第j列 c[i+j]=1;//占领两个对角线 d[i-j+n]=1; if(i 数据结构课程设计报告 任务 要求 淮阴工学院 数据结构课程设计报告设计题目：八皇后 2008 年 6 月25 日 设计任务书 课题 名称 八皇后 设计目的1.用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既 攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现． 2.通过这次课程设计,提高自己的编程能力,熟悉c++的编程坏境,为以后的程 序开发打下基础. 实验环境1）系统要求：win98以上操作系统；2）语言平台：tc++或vc++6.0；3）执行文件：八皇后.exe 任务要求试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。 工作进度计划 序号起止日期工作内容 1 2008.6.23~2008.6.24查阅相关内容 2 2008.6.24~2008.6.25编写代码及实习报告 3 2008.6.25~2008.6.26完善课程设计报告 4 2008.6.26~2008.6.27答辩 指导教师（签章）： 2008 年 6 月30 日 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法 数据结构课程设计报告 八皇后问题 班级： *** 姓名： *** 学号： *** 八皇后问题 1、问题分析 八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850提出；在8X8格的国际象棋上摆放八皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后人有人用图论的方法解出92 宗结果。 八皇后问题是在8*8 的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。 八皇后在棋盘上分布的各种可能的格局，其数非常大，但是可以将一些明显不满足问题要求的格局排除掉。由于任何两个皇后不能同行，即每一行只能放置一个皇后，因此将第i 个皇后放置在第i 行。这样在放置第i 个皇后时，只要考虑它与前i-1 个皇后处于不同列和不同对角线位置上即可。 2、算法描述 从第一行起逐行放置皇后，每放置一个皇后均需要依次对第1, 2…8列进 行 试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已经放置的其他皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列位置不安全，则用下一列去试探，当8 列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置，然后继续试探。 该算法抽象的描述如下： (1)置当前行当前列均为1； (2) While (当前行号v= 8); ( 3) {检查当前行，从当前列起逐列试探，寻找安全列号； (4) if (找到安全列号) ( 5)放置皇后，将列号放入栈中，并将下一行置为当前行，第 1 列置为当前列； ( 6) else ( 7)退栈回溯到上一行，移去该行已经放置的皇后，已该皇后所在列的下一列作为当前列； ( 8) } 2．1 算法求精 要对上述抽象算法进行逐步求精，就需要确定相应的存储结构和有关的数据类型。当前行和列分别用i和j表示；用数组s[1…8表示顺序栈，栈空间的下标值表示皇后所在的行号，栈的内容是皇后所在的列号。例如，若皇后放在位置(i,j)上，则将j压入栈中，即s[i]=j。为了便于检查皇后之间是否冲突，我们增加三个布尔数组(初始值为真)，将与检查有关的信息事先保存起来。定义如下： int a[9],b[17],c[17]; int s[9]; 其中，a[j]为真时 递归算法——八皇后问题 1、背景问题描述 八皇后问题是一个古老而著名的问题，该问题的目标是在8×8的国际象棋棋盘上放置八个皇后，使得任意两个皇后都不在同一行，或同一列或同一对角线上。如图1所示就是八皇后问题的一个解。 图1 八皇后问题的一个解 1854年在柏林的象棋杂志上不同的作者发表了40种不同的解。大数学家高斯认为有76种不同的方案。后来有人用图论的方法算出92种不同的解。 能否利用程序算出所有满足条件的解的数目呢？ 2、抽象表示及存储 对于这种矩形排列的棋盘而言，用二维数组存储棋盘的状况是最容易想到的方法。可以设置一个8*8的二维数组，令有棋子的位置为1，无棋子的部分为0。 事实上，由于8个皇后中任意两个皇后都不在同一行，因此8个皇后只能各自占据一行。不妨认为8个皇后编号为0、1、……、7，它们各自占据棋盘的第1行、第2行、……、第8行。从而可以使用长度为8一维数组表示棋盘状态，数组元素的下标表示棋子所在行，数组元素的值表示各个棋子所在的列。 使用的存储方式不同，其采用的算法已有很大区别。 3、问题分析及算法设计 假定用二维数组A存储棋盘的情况，可以考虑下面两种思路。 思路一：不考虑任何限制的穷举法。 用8×8的二维数组存储棋盘，若在(i,j)处有子，则令A[i][j]=1，否则A[i][j]=0。于是8个棋子第1个有64种摆放方法，第2个有63种放法，……，第8个有57种放法，则所有摆放方法有64×63×62×…×57种。可以列举每一种摆法，而后考察每种方法是否符合条件。这个计算量非常大。 思路二：考虑经过优化的穷举法(二维数组方案)。 若8个棋子位于8行8列的棋盘中，要求任意两个不同行、不同列，则任一解必然是各行、各列只包含一个棋子，其它情况必然不是解。于是可以做个8重循环，把每个皇后安排在每行的每个位置都试一遍。算法如下： 将整个棋盘数组赋值为0； for(1号皇后从1行1列到1行8列) { 将1号皇后能控制的线路(横向、竖线、斜线)全部设为1； for(2号皇后从2行1列到2行8列) { if(2号皇后控制的线路全部为0) { 将2号皇后能控制的线路(横向、竖线、斜线)全部设为2； for(3号皇后从3行1列到3行8列) { if(3号皇后控制的线路全部为0) { 将3号皇后能控制的线路全部设为3； …… for(8号皇后从8行1列到8行8列) { if(8号皇后控制的线路全部为0) { 将8号皇后能控制的线路全部设为8； 记录该棋盘为一个解； } 将8号皇后控制的线路全部恢复为0； } …… } 将3号皇后控制的线路全部恢复为0； } } 将2号皇后控制的线路全部恢复为0； } 将1号皇后控制的线路全部恢复为0 } 上述算法中的多重循环虽易于理解，但程序嵌套结构较为复杂，形式死板，不易扩展。事实上，可以将某一个棋子在一行中的试探过程写成一个递归函数，这样程序的灵活性就大为提高了。 对于本问题实际上还可以用一维数组的存储形式解决，下面的思路正是如此。 思路三：考虑经过优化的穷举法(一维数组方案)。 在思路二的算法中，摆放第i行棋子时，判断可行性的方法是考察第i个棋子的控制区域是否和第1到第i-1个棋子的控制区域是否有交叉。现在将判断可行性方法改变如下：算法实验 递归回溯解八皇后问题
八皇后问题算法分析
八皇后问题的解决完整文档
八皇后问题及解答
8皇后问题matlab算法
八皇后问题讲解
回溯法解八皇后问题
八皇后问题(回溯法)
八皇后问题 C语言程序设计
数据结构课程设计之_八皇后问题
八皇后问题的解决完整文档
算法设计与分析实验报告—八皇后问题
数据结构课程设计之八皇后问题
八皇后问题JAVA程序
n皇后问题算法设计
八皇后问题数据结构课程设计报告
八皇后问题
设计任务书
课题 八皇后 名称 1. 2. 3. 4. 调研并熟悉八皇后的基本功能、数据流程与工作规程； 学习八皇后相关的算法和基于 VC++集成环境的编程技术； 通过实际编程加深对基础知识的理解，提高实践能力； 学习开发资料的收集与整理，学会撰写课程设计报告。
设计 目的
实验 环境
1. 微型电子计算机（PC）； 2. 安装 Windows 2000 以上操作系统，Visual C++6.0 开发工具。
1. 利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设 计要求，注意材料收集与整理； 2. 在第 16 周末之前完成预设计，并请指导教师审查，通过后方可进行下一 步工作； 3. 本课题要求至少用三种方法解决八皇后问题，输入棋盘的阶层，然后显示 共有多少种布局方案，并显示每一种方案的具体情况。 4. 结束后，及时提交设计报告（含纸质稿、电子稿），要求格式规范、内容 完整、结论正确，正文字数不少于 3000 字（不含代码）。 工作进度计划 起止日期 工 作 内 容
序号
1
2009.06.7~2009.06.7
在预设计的基础上， 进一步查阅资料， 完善设计方案， 形成书面材料。 设计总体方案，构建、绘制流程框图，编写代码，上 机调试。
2
2009.06. 7~2009.06.10 2009.06.11~2009.06.1 2 2009.06.12~2009.06.1 3
3
测试程序，优化代码，增强功能，撰写设计报告。
4
提交软件代码、设计报告，参加答辩，根据教师反馈 意见，修改、完善设计报告。
指导教师（签章）：
年
月
日
摘要： 众所周知的八皇后问题是一个非常古老的问题，具体如下：在 8*8 的国际象棋棋 盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处 于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。要求编写实现八 皇后问题的递归解法或非递归解法，对于任意给定的一个初始位置，输出八皇后问题 的一个布局。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及 变通能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题 和解决问题的作风和能力。八皇后问题的解决完整文档
八皇后问题
8皇后问题分析与解法
相关主题
文本预览