数据结构课程设计
题目：八皇后问题
指导教师：胡*
学生院系：数学学院
学生班级：信计*班
学生姓名：黎*文
学生学号： 14070204**
2016年12月30日
目录
一.功能以及需求分析 (3)
1.1 问题的由来和背景 (3)
1.2 问题的基本解决思路 (3)
1.3 问题的应用 (3)
二.总体设计 (4)
2.1 运行环境 (4)
2.2 程序框架 (4)
2.3 算法分析 (4)
2.3.1 总体算法分析 (4)
2.3.2 非递归算法分析 (6)
2.3.3 递归算法的分析 (6)
三.详细设计 (6)
3.1 递归法的详细设计 (6)
3.2 非递归法的详细设计 (8)
四.具体实现及运行 (10)
4.1 QueenMainl类的实现： (10)
4.2 QueenNR类： (10)
4.3 QueenRS类： (11)
4.4 C语言程序： (11)
五. 总结 (12)
六.代码清单 (13)
6.1 Java代码： (13)
6.2 C语言源代码： (20)
一.功能以及需求分析
1.1 问题的由来和背景
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。
1.2 问题的基本解决思路
八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法。
八皇后问题出现在1990年代初期的著名电子游戏第七访客中。设置一个三维数组，第一个下标是皇后的行坐标，第二个下标是皇后的列坐标，第三个下标是残卷号。相当于有N张叠在一起的8*8棋盘，每张棋盘只在复制前面棋盘及皇后后加放置一个皇后。直到放满8皇后后才是一张完整的8皇后图，称完卷。这里实际操作时多加一行多加一列即第0行第0列，但这一行/列不作输出，只是作此行/列有无皇后的参考。
总的来说现在解八皇后问题的总体算法都是采用回溯法，也叫作穷搜法，再穷搜的时候去掉分支，减少不必要的运算，对于八皇后问题的求解，一般只能做出15皇后问题，有部分算法高手在有精良设备的情况下算出了25皇后的解。受算法和硬件计算能力的影响，因为计算量为O(n!)，而且回溯法使用的内存空间特别大，所以此问题的求解还有很多可以探究的地方，尤其是算法上的改进。
1.3 问题的应用
八皇后问题可以用来解决地图的着色问题，以及迷宫的求解问题，同时，八皇后问题是一个典型的回溯法求解问题，可以用它来类比很多和回溯法有关的问题。对于现在的DNA序列问题也可以从中得到启发。
二.总体设计
2.1 运行环境
（1）编译环境：JDK 1.8 ，以及eclipse ，Mars 4.5.2，Visual C++ 6.0 （2）电脑系统： Windows server 2003 32位
（3）编译语言：Java，C语言
2.2 程序框架
（1）MainQueen：实现可视化界面，可以选择递归和非递归两种算法得到八皇后问题的解，并将答案打印出来。
（2）QueenNR：采用非递归方法求解问题。
（3）QueenRS：采用递归方法求解问题。
（4）编译C语言程序。
2.3 算法分析
2.3.1 总体算法分析
算法的核心是回溯法，也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。为了能够撤销当前的求解过程，必须保存上一步以来的求解路径。当撤销之后满足条件，就一直做下去，直到试探完所有的可能解。
总结如下：
(1)设置初始化的方案（给变量赋初值，读入已知数据等）。
(2)变换方式去试探，若全部试完则转(7)。
(3)判断此法是否成功（通过约束函数），不成功则转(2)。
(4)试探成功则前进一步再试探。
(5)正确方案还未找到则转(2)。
(6)已找到一种方案则记录并打印。
(7)退回一步（回溯），若未退到头则转(2)。
(8)已退到头则结束或打印无解
另外一个关键就是对于每一个部分解的判定，可归纳问题的条件为:
1.不在同一行（列）上
2.不在同一斜线上
3.不在同一反斜线上
具体到八皇后的问题，我们可以逐行或者逐列来进行可行摆放方案的遍历，每一行（或列）遍历出一个符合条件的位置，接着就到下一行或列遍历下一个棋子的合适位置，这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的——就是下一个棋子的摆放位置与前面的棋子不在同一行（或列）。接下来，我们只要判断当前位置是否还符合其他条件，如果符合，就遍历下一行（或列）所有位置，看看是否继续有符合条件的位置，以此类推，如果某一个行（或列）的所有位置都不合适，就返回上一行（或列）继续该行（或列）的其他位置遍历，当我们顺利遍历到最后一行（或列），且有符合条件的位置时，就是一个可行的8皇后摆放方案，累加一次八皇后可行方案的个数，然后继续遍历该行其他位置是否有合适的，如果没有，则返回上一行，遍历该行其他位置，依此下去。这样一个过程下来，我们就可以得出所有符合条件的8皇后摆放方案了。这是一个深度优先遍历的过程，同时也是经典的递归思路。
接下来，我们以逐列遍历，具体到代码，进一步说明。首先，从第一列开始找第一颗棋子的合适位置，我们知道，此时第一列的任何一个位置都是合适的，当棋子找到第一个合适的位置后，就开始到下一列考虑下一个合适的位置，此时，第二列的第一行及第二行显然就不能放第二颗棋子了，因为其与第一个棋子一个同在一行，一个同在一条斜线上。第二列第三行成为第二列第一个合适的位置，以此类推，第三列的第5行又会是一个合适位置，这个过程中，我们注意到，每一列的合适位置都是受到前面几列的位置所影响，归纳如下：
假设前面1列的棋子放在第3行，那当前列不能放的位置就一定是3行，2行，4行。因为如果放在这三行上就分别跟前一列的棋子同在一行、同在斜线、同在反斜线上，不符合我们的要求。现在我们用cols数组来表示8个列棋子所放的行数，数组下标从0开始，其中数组下标表示列数，数组的元素值表示该列棋子所在行数，当前列为N（N>=0,N cols[N] != cols[N-1]（=3，表示不在同一行） cols[N] != cols[N-1]-1（=3-1=2，表示不在同一斜线上) ols[N]!=cols[N-1]+1(=3+1,表示不在同一反斜线上) 这里我们注意到，如果N-2列存在的话，那么我们还要考虑当前列N不与N-2列的棋子同行，同斜线，同反斜线。把当前列N的前面的某一列设为m,则m 的所有取值为｛m>=0,m cols[N] != cols[m]（与第m列的棋子不在同一行） cols[N] != cols--[m] -（N-m）(>=0 ,与第m列的棋子不在同一斜线上) cols[N] != cols--[m] + (N-m) (<=8-1,与第m列的棋子不在同一反斜线上) 为了使此程序能够解决N皇后的问题，一般将参数改成N，已解决N皇后的问题，当然，这还和计算机性能和算法差异有关，此程序一般能解决到15皇后的问题。在Java程序中以实现N皇后问题。 2.3.2 非递归算法分析 程序首先对N行中的每一行进行探测，寻找该行中可以放置皇后的位置，具体方法是对该行的每一列进行探测，看是否可以放置皇后，如果可以，则在该列放置一个皇后，然后继续探测下一行的皇后位置。如果已经探测完所有的列都没有找到可以放置皇后的列，此时就应该回溯，把上一行皇后的位置往后移一列，如果上一行皇后移动后也找不到位置，则继续回溯直至某一行找到皇后的位置或回溯到第一行，如果第一行皇后也无法找到可以放置皇后的位置，则说明已经找到所有的解程序终止。如果该行已经是最后一行，则探测完该行后，如果找到放置皇后的位置，则说明找到一个结果，打印出来。但是此时并不能再此处结束程序，因为我们要找的是所有N皇后问题所有的解，此时应该清除该行的皇后，从当前放置皇后列数的下一列继续探测。 2.3.3 递归算法的分析 第1次考虑把皇后放在第1行的某个位置，第2次放的时候就不用去放在第一行了，因为这样放皇后间是可以互相攻击的。第2次我就考虑把皇后放在第2行的某个位置，第3次我考虑把皇后放在第3行的某个位置，这样依次去递归。每计算1行，递归一次，每次递归里面考虑8列，即对每一行皇后有8个可能的位置可以放。找到一个与前面行的皇后都不会互相攻击的位置，然后再递归进入下一行。找到一组可行解即可输出，然后程序回溯去找下一组可靠解。 用一个一维数组来表示相应行对应的列，比如cols[i]=j表示，第i行的皇后放在第j列。如果当前行是r，皇后放在哪一列呢？cols[r]列。一共有8列，所以我们要让cols[r]依次取第0列，第1列，第2列……一直到第7列，每取一次我们就去考虑，皇后放的位置会不会和前面已经放了的皇后有冲突。怎样是有冲突呢？同行，同列，对角线。由于已经不会同行了，所以不用考虑这一点。只有满足了当前皇后和前面所有的皇后都不会互相攻击的时候，才能进入下一级递归。 三.详细设计 3.1 递归法的详细设计 （1）定义一个cols[]数组，存储八皇后问题中每一列（j）对应放置的皇后的位置（i）。 （2）定义getArrangement(int n) 递归函数，其中定义一个boolean型rows[]数组，记录每一行能够正常放置的位置，如果能放置，设置为true，默认为null。函数中，先找出每列合适的的第一个位置。然后判断是不是最后一列，是最后一列就输出，不是就进入递归。如果该列没找到一个合适的位置，跳出此次递归，进入上一次递归。 具体函数如下： public void getArrangement(int n){ //遍历该列所有不合法的行，并用rows数组记录，不合法即rows[i]=true boolean[] rows = new boolean[MAXQUEEN]; //判断该点是不是合法，如果有合法的，不赋值为 null for(int i=0;i // 判断行是否合法 rows[cols[i]]=true; int d = n-i; //判断左右斜线是否合法 if(cols[i]-d >= 0) rows[cols[i]-d]=true; if(cols[i]+d <= MAXQUEEN-1) rows[cols[i]+d]=true; } for(int i=0;i //判断该行是否合法合法就跳出选出第一个可以添加的行 if(rows[i])continue; cols[n] = i; //设置当前列合法棋子所在行数 if(n getArrangement(n+1); }else{ num++; //累计方案个数 printChessBoard();//打印棋盘信息 } } } （3）定义输出函数public void printChessBoard()，输出函数比较简单，利用全部赋值之后clos数组，序号代表列，序列的值代表行。两个for循环即可输出。‘+’代表空，‘0’代表皇后。具体函数如下： public void printChessBoard(){ System.out.print("第"+num+"种走法 \n"); for(int i=0;i for(int j=0;j if(i==cols[j]){ System.out.print("0 "); }else System.out.print("+ "); } System.out.print("\n"); } } 3.2 非递归法的详细设计 （1）定义一个flag[n][n]数组，作为存储皇后位置。定义record[2][n]数组作为回溯步骤，其中record[0][n]记录序号对应行的位置，record[1][n]，记录序号对应列的位置。多几个数组便于理解和回溯。 （2）定义reset(int[][] flag)函数，将数组flag全部初始化为-1；代码略。（3）定义 isTrue(int[][] record, int m, int n) 判断函数。判断对应的点能否放置皇后。采用了和递归法中不一样的思路，将判断独立成一个函数，利用记录数组和位置m,n判定。使得对点的判断更加直观。 public boolean isTrue(int[][] record, int m, int n) { int left = n-1,right = n+1,len=record[0].length; boolean f=true; if(m==0) return true; else{ for(int i=m;i>0;){ i--; if(record[1][i]==n){//是否同一列 f=false; break; } if(left>=0){ if(record[1][i]==left){//是否同一右斜 f=false; break; } else left--; } if(right<=len-1){ if(record[1][i]==right){//是否同一左斜 f=false; break; } else right++; } } } （4）定义 parseQueen( int[][] flag,int[][] record) 核心回溯函数。 public void parseQueen( int[][] flag,int[][] record) { int i=0,j=0,len=flag.length; //System.out.println("length="+len); while(true){ if(record[1][i]!=-1){//判断当前点是否为上次退行的位置，是则进行再定位 //清除原来在回溯一行定位的点 j=record[1][i]; record[1][i]=-1; flag[i][j]=-1; //把回溯点的值改为-1 if(j else{ if(i>0) i--;//往上移 else {/*System.out.println("iojhipo");*/ //在此 结束回溯 return ; }//结束 } } else{//当前点为普通点 if(!isTrue(record,i,j)){//该定位点位置不满足要求 if(j else{ if(i>0) i--;//往上找定位点 else {/*System.out.println("iojhipo");*/return ;}//结束 } } else{//该定位点位置满足要求 //放置定位点 flag[i][j]=1; record[0][i]=i; record[1][i]=j; if(i i++; j=0; } //end if else{//到末尾，找到一条路径 isExist=true; printArray(flag);//打印 record[1][i]=-1;//做回溯处理准备 flag[i][j]=-1; i--;//往上继续搜寻 } //end else } } } } （5）定义输出函数 rintArray(int[][] flag)，代码略（见代码清单）。 注明：C语言程序的分析和上述类似，不在赘述。 四.具体实现及运行 4.1 QueenMainl类的实现： 4.2 QueenNR类： 实现了QueenMain类的非递归按钮功能 4.3 QueenRS类： 实现了QueenMain类的递归按钮功能 4.4 C语言程序： 五.总结 1. 八皇后问题的求解计算量是特别大的，对于非递归算法，由于等价于穷搜法，他的时间复杂度约等于O(n！) ，即是n的全排列。虽然采用了去除分支的办法，但是对于总体来说，并不会减少太多运算，所以对于这种大型的计算。还需要改进算法，并且需要硬件的支持。本实验一般只能解决到12皇后，而且计算时间都比较长。 2. 对于递归算法，效率比较低，但是便于理解，方便写代码。 3. 对于两个算法的比较，都是用的回溯法，只是在具体的回溯方法上的区别。 4. 八皇后问题在实际的生活中有很多的得到实用的地方，熟练地掌握八皇后问题的求解过程，能解决很多实际中的算法问题。比如迷宫问题和地图着色问题，都可以应用相应的算法。 六.代码清单 6.1 Java代码： QueenMainl类： package com.Listen; import java.awt.BorderLayout; import java.awt.CardLayout; import java.awt.Container; import java.awt.Font; import java.awt.GridLayout; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import javax.swing.BoxLayout; import javax.swing.JButton; import javax.swing.JFrame; import javax.swing.JLabel; import javax.swing.JPanel; import javax.swing.JScrollPane; import javax.swing.JTextArea; import javax.swing.JTextField; public class QueenMain extends JFrame implements ActionListener{ JPanel topPanel = new JPanel(); JButton jb1, jb2, jb3; JTextArea jta = null; JScrollPane jscrollPane; JLabel inputLabel; JTextField inputNum; JPanel panel1,panel2; String s ="请在上方输入4--10的数查看八皇后路径问题："; public QueenMain() { setLayout(new BorderLayout()); // 设置按钮 panel1 = new JPanel();panel2 = new JPanel();topPanel = new JPanel(); inputLabel = new JLabel("请输入数字："); inputNum = new JTextField(25); panel1.add(inputLabel);panel1.add(inputNum); //topPanel.setLayout( BoxLayout.Y_AXIS); topPanel.setLayout(new BoxLayout(topPanel, BoxLayout.Y_AXIS)); topPanel.add(panel1); jb1 = new JButton("递归"); jb1.addActionListener((ActionListener) this); jb2 = new JButton("非递归"); jb2.addActionListener((ActionListener) this); jb3 = new JButton("清空"); jb3.addActionListener((ActionListener) this); //添加按钮 panel2.setLayout(new GridLayout(1, 3)); panel2.add(jb1);panel2.add(jb2);panel2.add(jb3); topPanel.add(panel2); add(topPanel,BorderLayout.NORTH); jta = new JTextArea(10, 15); jta.setText(s); jta.setEditable(false); jta.setTabSize(4); jta.setFont(new Font("标楷体", Font.BOLD, 16)); jta.setLineWrap(true);// 激活自动换行功能 jta.setWrapStyleWord(true);// 激活断行不断字功能 jscrollPane = new JScrollPane(jta); add(jscrollPane ,BorderLayout.CENTER); } private void QueenRs() { int n =Integer.parseInt(inputNum.getText()) ; QueenRST qr = new QueenRST(n,this); } private void QueenNr() { int n =Integer.parseInt(inputNum.getText()) ; QueenRST qr = new QueenRST(n,this); } public static void main(String[] args) { QueenMain app = new QueenMain(); app.setTitle("八皇后问题"); app.setVisible(true); app.setBounds(300,100,400,600); app.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); } public void actionPerformed(ActionEvent e) { if (e.getSource() == jb1) { this.jta.setText(null); QueenRs(); } if(e.getSource() == jb2){ this.jta.setText(null); QueenNr(); } if(e.getSource() == jb3){ this.inputNum.setText(null); this.jta.setText(s); } } } QueenNS类： package com.Listen; import java.util.Scanner; public class QueenNR { public int count=0; public boolean isExist=false; public int MAXQUEEN; public int [][] flag;//为解空间的值，即各个N*N方格的值 public int [][] record;// 2*N ,第一行记录每一行对应的列，第二行记录对应的回溯点（每一列对应的值） //构造函数 public QueenNR(int n){ MAXQUEEN=n;//赋初始值 flag=new int[MAXQUEEN][MAXQUEEN];//定义判断数组 record=new int[2][MAXQUEEN]; //定义记录数组 reset(flag); reset(record); //初始化 parseQueen(flag,record); } public void reset(int[][] flag) { int i,j,m=flag.length,n=flag[0].length; for( i=0;i for(j=0;j flag[i][j]=-1; } } //定义核心算法 public void parseQueen( int[][] flag,int[][] record) { int i=0,j=0,len=flag.length; //System.out.println("length="+len); while(true){ if(record[1][i]!=-1){//判断当前点是否为上次退行的位置，是则进行再定位 //清除原来在回溯一行定位的点 j=record[1][i]; record[1][i]=-1; flag[i][j]=-1; //把回溯点的值改为-1 if(j else{ if(i>0) i--;//往上移 else {/*System.out.println("iojhipo");*/ //在此结束回溯 return ; }//结束 } } else{//当前点为普通点 if(!isTrue(record,i,j)){//该定位点位置不满足要求 if(j else{ if(i>0) i--;//往上找定位点 else {/*System.out.println("iojhipo");*/return ;}//结束 } } else{//该定位点位置满足要求 //放置定位点 flag[i][j]=1; record[0][i]=i; record[1][i]=j; if(i i++; j=0; } //end if else{//到末尾，找到一条路径 isExist=true; printArray(flag);//打印 record[1][i]=-1;//做回溯处理准备 flag[i][j]=-1; /* if(i==0)//结束 return ; */ i--;//往上继续搜寻 } //end else } } } } //判断函数： public boolean isTrue(int[][] record, int m, int n) { int left = n-1,right = n+1,len=record[0].length; boolean f=true; if(m==0) return true; else{ for(int i=m;i>0;){ i--; if(record[1][i]==n){//是否同一列 f=false; break; } if(left>=0){ if(record[1][i]==left){//是否同一右斜 f=false; break; } else left--; } if(right<=len-1){ if(record[1][i]==right){//是否同一左斜 f=false; break; } else right++; } } } return f; } //输出函数： public void printArray(int[][] flag) { int i,j,len=flag.length,len2=flag[0].length; count++; System.out.println("这是第"+count+"路径："); for( i=0;i for(j=0;j if(flag[i][j]==-1) System.out.print("+ "); else System.out.print("0 "); } System.out.println(); } System.out.println(); //reset(flag); } /* public void printArray(int[][] record) { count++; System.out.print("第"+count+"种走法 \n"); for(int i=0;i for(int j=0;j if(i==record[0][j]){ System.out.print("0 "); }else System.out.print("+ "); } System.out.println("\n"); } }*/ //测试函数： public static void main(String []args) { Scanner in=new Scanner(System.in); System.out.println("请输入八皇后问题中‘n’的值(n>=4):"); QueenNR app = new QueenNR(in.nextInt()); System.out.println("皇后有"+app.count+"条路径"); in.close(); } } QueenRS类： package com.Listen; import java.util.Scanner; public class QueenRS { public int num = 0; //累计方案总数 public int MAXQUEEN ;//皇后个数，同时也是棋盘行列总数 public int[] cols; //定义cols数组，表示8列棋子摆放情况 public QueenRS(int n) { MAXQUEEN = n; cols = new int[MAXQUEEN]; //核心函数 getArrangement(0); System.out.print("\n"); System.out.println(MAXQUEEN+"皇后问题有"+num+"种摆放方法。"); } //核心函数代码 public void getArrangement(int n){ //遍历该列所有不合法的行，并用rows数组记录，不合法即rows[i]=true boolean[] rows = new boolean[MAXQUEEN]; //判断该点是不是合法，如果有合法的，不赋值为 null for(int i=0;i // 判断行是否合法 rows[cols[i]]=true; int d = n-i; //判断左右斜线是否合法 if(cols[i]-d >= 0) rows[cols[i]-d]=true; if(cols[i]+d <= MAXQUEEN-1) rows[cols[i]+d]=true; } for(int i=0;i //判断该行是否合法合法就跳出选出第一个可以添加的行 if(rows[i])continue; //设置当前列合法棋子所在行数 cols[n] = i; //当前列不为最后一列时 if(n getArrangement(n+1); }else{ num++; //累计方案个数 printChessBoard();//打印棋盘信息 } } } //打印函数 public void printChessBoard(){ System.out.print("第"+num+"种走法 \n"); for(int i=0;i for(int j=0;j if(i==cols[j]){ System.out.print("0 "); }else System.out.print("+ "); } System.out.print("\n"); } } //测试代码 public static void main(String args[]){ Scanner in = new Scanner(System.in); System.out.println("请输入八皇后问题中‘n’的值(n>=4):"); QueenRS queen = new QueenRS(in.nextInt()); } } 6.2 C语言源代码： //八皇后问题 #include #include //输出0代表皇后 void printFF(int *position){ int i=0,j=0; for(i = 0; i < 8; ++i) { for(j = 0; j < 8; ++j) { if(position[i] == j) printf("0 "); else printf("+ "); } printf("\n"); } printf("\n"); } //非递归算法 void empress(int *count,int *position) { int i, j, flag; while(position[8] != 1) { ++position[0]; for(i = 0; i < 8; ++i) { if(position[i] == 8) { position[i] = 0; ++position[i+1]; } } flag = 1; //判断结果是否满足条件 for(i = 0; i < 8; ++i) { for(j = 0; j < 8; ++j) 工学院 数据结构课程设计报告设计题目：八皇后 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. 需求分析 丽水学院计算机实验报告 丽水学院计算机实验报告 一、实验目的 1.熟悉Visual C++和C-Free等集成环境，掌握运行一个C程序的基本步骤，包括编辑、编译、连接和运行。 2.掌握算术表达式和赋值表达式的使用。 3.掌握基本输入、输出函数的使用。 4.能够编程实现简单的数据处理。 二、实验环境 硬件：Pentium以上的计算机。 软件：Windows XP操作系统、Visual C++和C-Free等集成环境。 三、实验内容和结果 1.编程题1 在屏幕上显示一个短句“What is a computer?” 思考： （1）如何在屏幕上显示你自己的学号，姓名和班级？ （2）如何在屏幕上显示数字、英文字母和汉字等信息？例如：“你在机房吗？” 编程题1源程序： #include<> void main() { printf("What is a computer?\n"); } 程序运行结果： What is a computer? 思考题（1）： #include<> void main() { printf(",小王，班级\n"); } 思考题（2）： #include<> void main() { printf("英文字母abcdefgABCDEFG\n"); printf("汉字：哇哈哈啊哈和\n"); } 2.编程题2 在屏幕上显示下列图形。 * * * * * * * * * * 思考：如何在屏幕上显示下列图形？ A A A A 编程题2源程序： #include<> void main() { int i,j; for(j=1;j<5;j++) { for(i=5;i>j;i--) printf("*"); printf("\n"); } } 程序运行结果： * * * * * * * * * * 思考题： 深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：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 C语言实验报告参考答案 实验一熟悉C语言程序开发环境及数据描述 四、程序清单 1．编写程序实现在屏幕上显示以下结果： The dress is long The shoes are big The trousers are black 答案： #include<> main() { p rintf("The dress is long\n"); p rintf("The shoes are big\n"); p rintf("The trousers are black\n"); } 2．编写程序： (1) a=150,b=20,c=45,编写求a/b、a/c(商)和a%b、a%c(余数)的程序。 (2)a=160,b=46,c=18,d=170, 编写求(a+b)/(b-c)*(c-d)的程序。 答案： （1） #include<> main() { i nt a,b,c,x,y; a=150; b=20; c=45; x=a/b; y=a/c; p rintf("a/b的商=%d\n",x); p rintf("a/c的商=%d\n",y); x=a%b; y=a%c; p rintf("a/b的余数=%d\n",x); p rintf("a/c的余数=%d\n",y); } （2） #include<> main() { i nt a,b,c,d; f loat x; a=160; b=46; c=18; d=170; x=(a+b)/(b-c)*(c-d); p rintf("(a+b)/(b-c)*(c-d)=%f\n",x); } 3. 设变量a的值为0，b的值为-10，编写程序：当a>b时，将b赋给c；当a<=b时，将0赋给c。(提示：用条件运算符) 答案： #include<> main() { i nt a,b,c; a=0; b=-10; c= (a>b) b:a; p rintf("c = %d\n",c); } 五、调试和测试结果 1.编译、连接无错，运行后屏幕上显示以下结果： The dress is long The shoes are big The trousers are black 2、(1) 编译、连接无错，运行后屏幕上显示以下结果： a/b的商=7 a/c的商=3 数据结构课程设计 选题：八皇后问题 姓名： 学号： 指导老师： 目录 一.选题概述---------------------------------------3 二.设计要求与分析--------------------------------3 三.数据结构与定义--------------------------------4 1.结构体定义 2.函数定义 3.函数之间的定义 四.程序段与分析----------------------------------5 五.完整程序代码及运行结果截图------------------7 六.心得体会--------------------------------------10 七.参考文献--------------------------------------10 一．选题概述： 在实际应用中，有相当一类问题需要找出它的解集合，或者要求找出某些约束条件下的最优解。求解时经常使用一种称为回溯的方法来解决。所谓回溯就是走回头路，该方法是在一定的约束条件下试探地搜索前进，若前进中受阻，则回头另择通路继续搜索。为了能够沿着原路逆序回退，需用栈来保存曾经到达的每一个状态，栈顶的状态即为回退的第一站，因此回溯法均可利用栈来实现。而解决八皇后问题就是利用回溯法和栈来实现的。 二．设计要求与分析 八皇后问题是在8x8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。 八皇后在棋盘上分布的各种可能的格局，其数目非常大，约等于232种，但是，可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行上。这样在放置第i个皇后时，只要考虑它与前i 一1个皇后处于不同列和不同对角线位置上即可。因此，其算法基本思想如下： 从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1，2，…，8列进行试探，并尽可能取小的列数。若当前试探的列位置 《C语言程序设计实训1》报告 设计题目：基于数组的学生信息管理系统学院名称：信息科学技术学院 专业：计算机科学与技术 班级： 姓名：学号 指导教师： 提交日期： 2014年12月22日 一、实验内容 编写并调试程序，实现学校各专业班级学生信息的管理。10个学生的信息存储在文件中。在头文件中定义学生信息的结构体类型，包括： 学号、姓名、专业、班级、3门成绩；和符号常量N（学生数）。（同一班 级的学生可以属于不同的专业，同一专业的学生可以属于不同的班级） 二、实验要求 (1)main函数：以菜单形式将各项功能提供给用户，根据用户的选择， 调用相应的函数。 STU student[N]; 函数 #include "" void main() { int i,n,id,num,m,sub,corse;将从文件中读取10个人的信\n"); printf("\n2.您将从文件中随机读取第n(0<=n<=9)个学生的信息\n") printf("\n3.您将根据某一班级某一专业总分超过多少进行查找\n"); printf("\n4.您将求某一课程分数最高的学生序号的下标\n"); printf("\n5.您将对平均成绩由低到高进行简单选择排序法\n "); printf("\n6.您将对某一个班的平均成绩由低到高进行起泡排序法\n"); printf("\n7.您将对某门专业的学生的某门课程成绩由低到高进行直接插入排序法\n"); printf("\n8.您将把学生信息存入文件\n"); scanf("%d",&id); getchar(); switch(id){ case 1: { printf("\n从文件中读取信息\n"); Input(students,sizeof(students)/sizeof(STU));Sort_select 函数 #include "" void Sort_select(STU * p) { int i,j,k; float sum,ave[N],t; STU tem; for(i=0;i 数据结构实验报告 实验名称：实验二——利用栈结构实现八皇后问题 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月21日 1．实验要求 （1）实验目的 通过选择下面五个题目之一进行实现，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力 （2）实验内容 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 ①可以使用递归或非递归两种方法实现 ②实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线。 （3）代码要求 ①必须要有异常处理，比如删除空链表时需要抛出异常； ②保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 ③递归程序注意调用的过程，防止栈溢出 2. 程序分析 2.1 存储结构 栈（递归）： 2.2 关键算法分析 (1)递归 void SeqStack C语言实验报告 说明 1，所有程序均用VC6.0编译运行，文件名命名为姓名+日期，因为实验存在补做，所以并不是按照日期先后排列的。 2，为了使截图清晰，手动将运行窗口由“黑底白字”改为了“白底黑字”。 实验2 数据类型、运算符和表达式 一、实验目的： （1）掌握C语言数据类型，熟悉如何定义一个整型、字符型、实型变量、以及对它们赋值的方法。 （2）学会使用C的有关算术运算符，以及包含这些运算符的表达式，特别是自加（++）和自减（――）运算符的使用。 （3）掌握C语言的输入和输出函数的使用 （4）进一步熟悉C程序的编辑、编译、连接和运行的过程。 三、程序调试与问题解决： (1)输人并运行下面的程序 #include printf("%d %d\n",c1,c2); 再运行，并分析结果。 输出结果如图，编译成功，无错误。 ○3将第3行改为 int c1,c2; 再运行，并分析结果。 ○4再将第4、5行改为 c1=a; c2=b; 再运行，并分析结果。 a,b没有定义，编译报错。 ○5再将第4、5行改为 c1=‘’a‘’; c2=‘’b‘’; 再运行，并分析结果。 ○6再将第4、5行改为 c1=300; c2=400; 再运行，并分析结果。 以字符型输出时，输出的将是300，400对应的字符。 (2)输人并运行教材第3章习题3. 6给出的程序 #include 1．实验要求 【实验目的】 1、进一步掌握指针、模板类、异常处理的使用 2、掌握栈的操作的实现方法 3、掌握队列的操作的实现方法 4、学习使用栈解决实际问题的能力 5、学习使用队列解决实际问题的能力 【实验内容】 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 提示： 1、可以使用递归或非递归两种方法实现 2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析 2.1 存储结构 存储结构：栈（递归） 2.2 关键算法分析 【设计思想】 由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法 【伪代码】 1、输入皇后个数n 2、k=1 3、判断k是否大于n 3.1 是：打印一组可能 3.2 否：循环行位置1~n 判断该位置是否符合要求，若符合记录q[k]的坐标y值 k+1 重复3 【关键算法】 1、递归 void Queen::Queens(int k,int n) { int i; if(k>n) { Print(n); count(); } else { for(i=1;i<=n;i++) if(Isavailable(i,k)) //判断该行中该位置放置‘皇后’是否符合要求 { q[k]=i; //记录改行中该点的位置 Queens(k+1,n); //放置下一行的‘皇后’ } } } 2、判断皇后放置位置是否符合要求 bool Queen::Isavailable(int i,int k) { int j; j=1; while(j 八皇后问题 问题描述： 在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相冲突 （在每一横列，竖列，斜列只有一个皇后）。 求解： 标题: 八皇后问题的解（回溯法程序代码） 发信站: 网易虚拟社区(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 淮阴工学院 数据结构课程设计报告 设计题目：八皇后 系（院）:计算机工程系 专业：信息安全 班级：信息 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) . 回溯算法与八皇后问题(N皇后问题) 1 问题描述 八皇后问题是数据结构与算法这一门课中经典的一个问题。下面再来看一下这个问题的描述。八皇后问题说的是在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。更通用的描述就是有没有可能在一张N*N的棋盘上安全地放N个皇后？ 2 回溯算法 回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。 下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘： 1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列 2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没 有两个皇后)，若不满足，跳到第4步 3) 在当前位置上满足条件的情形： 在当前位置放一个皇后，若当前行是最后一行，记录一个解； 若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置； 若当前行是最后一行，当前列不是最后一列，当前列设为下一列； 若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置； 以上返回到第2步 4) 在当前位置上不满足条件的情形： 若当前列不是最后一列，当前列设为下一列，返回到第2步; 若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步; 算法的基本原理是上面这个样子，但不同的是用的数据结构不同，检查某个位置是否满足条件的方法也不同。为了提高效率，有各种优化策略，如多线程，多分配内存表示棋盘等。 为了便于将上述算法编程实现，将它用另一种形式重写： Queen() Loop: if check_pos(curr_row, curr_col) == 1 then put_a_queen(curr_row, curr_col); if curr_row == N then record_a_solution(); end if; if curr_row != N then curr_row = curr_row + 1; curr_col = 1; else if curr_col != N then curr_col = curr_col + 1; else backtrack(); end if; end if; else if curr_col != N then 实验一进制转换一、实验要求 采用模块化程序设计完成进制转换。由键盘输入一个十进制正整数，然后将该数转换成指定的进制数(二、八、十六) 形式输出。指定的进制由用户输入。 二、实验目的 1、熟悉C 环境的安装、使用。 2、承上启下，复习《C 程序设计》等基础课程的知识。 3、掌握C 语言编程的方法。 三、预备知识 1、VC6.0的安装与使用。 2、C 程序设计基础知识。 四、实验内容 采用模块化程序设计完成进制转换。 五、程序框图 六、程序清单 1. 编写主函数：输入需转换的数与转换的进制 2. 编写子函数 （1）函数转换为除16进制以外的进制转换算数编程，使用while 循环实现计算进制 的转换，并输出转换后的数字； （2）函数转换为16进制，用while 函数实现16进制转换的计算并输出16进制转换后的数据； 3. 编写数组，关于16进制的一系列字符 4. 编写主函数加入do while 使函数可以循环。 七、实验步骤 #include } else { while(n) { a[++i]=num[n%16]; n/=16; } while(i!=-1) printf("%c",a[i--]); printf("\n"); } } int main() { int a, c; 如对您有帮助，请购买打赏，谢谢您！ 目录 一需求分析............................................ 错误！未定义书签。 1.1程序的功能：...................................... 错误！未定义书签。 1.2程序的输入输出要求：.............................. 错误！未定义书签。二概要设计............................................ 错误！未定义书签。 2.1程序的主要模块：.................................. 错误！未定义书签。 2.2程序涉及：........................................ 错误！未定义书签。三详细设计............................................. 错误！未定义书签。 3.1相关代码及算法..................................... 错误！未定义书签。 3.1.1 定义相关的数据类型如下：...................... 错误！未定义书签。 3.1.2 主模块类C码算法：............................. 错误！未定义书签。 3.1.3 画棋盘模块类C码算法........................... 错误！未定义书签。 3.1.4 画皇后模块类C码算法：........................ 错误！未定义书签。 3.1.5 八皇后摆法模块（递归法）：.................... 错误！未定义书签。 3.1.6 初始化模块.................................... 错误！未定义书签。 3.1.7 输出摆放好的八皇后图形（动态演示）：.......... 错误！未定义书签。 3.2相关流程图......................................... 错误！未定义书签。四调试分析............................................. 错误！未定义书签。五设计体会............................................ 错误！未定义书签。六附录................................................ 错误！未定义书签。七参考文献............................................ 错误！未定义书签。 回溯法解八皇后问题 在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 2016-2017学年第二学期 2016级专业：学号：姓名：……………………………………………………………………………………………… 一、实验题目：结构体和共用体 二、实验目的：（略） 三、实验内容 1．程序验证： 启动vc语言环境，输入并执行以下程序。 源代码：运行结果： #include 课程设计报告 课程名称数据结构课程设计 课题名称八皇后问题演示 专业通信工程 班级通信工程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.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块 的功能。 八皇后问题（回溯法）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 安徽省巢湖学院计算机与信息工程学院 课程设计报告 课程名称《数据结构》 课题名称八皇后问题 专业计算机科学与技术 班级 学号 姓名 联系方式 指导教师 2011 年 12 月 25日 目录 1、数据结构课程设计任务书.............................................................................................. １ 1.1、题目..................................................................................................................... １ 1.2、要求..................................................................................................................... １ 2、总体设计....................................................................................................................... １ 2.1、功能模块设计 ...................................................................................................... １ 2.2、所有功能模块的流程图........................................................................................ ２ 3、详细设计....................................................................................................................... ５ 3.1、程序中所采用的数据结构及存储结构的说明........................................................ ５ 3.2、算法的设计思想................................................................................................... ５ 3.3、稀疏矩阵各种运算的性质变换 ............................................................................. ５ 4、调试与测试：................................................................................................................ ６ 4.1、调试方法与步骤： ............................................................................................... ６ 4.2、测试结果的分析与讨论： .................................................................................... ６ 4.3、测试过程中遇到的主要问题及采取的解决措施：................................................. ６ 5、时间复杂度的分析：..................................................................................................... ６ 6、源程序清单和执行结果 ................................................................................................. ６ 7、C程序设计总结 ........................................................................................................ １０ 8、致谢.......................................................................................................................... １０ 9、参考文献................................................................................................................... １０八皇后问题的解决完整文档
c语言实验报告 ()
算法实验 递归回溯解八皇后问题
C语言实验报告参考答案(原)
数据结构课程设计报告-8皇后问题
C语言实验报告
数据结构实验报告利用栈结构实现八皇后问题
c语言实验报告
数据结构实验报告——栈(八皇后问题)
八皇后问题及解答
八皇后问题的解决完整文档
回溯算法与八皇后问题N皇后问题Word版
C语言实验报告
数据结构八皇后问题
回溯法解八皇后问题
C语言实验报告(八)
数据结构课程设计之_八皇后问题
八皇后问题(回溯法)
八皇后问题
相关主题
文本预览