《回溯法解决8皇后问题实验报告.docx》由会员分享，可在线阅读，更多相关《回溯法解决8皇后问题实验报告.docx（8页珍藏版）》请在三一办公上搜索。
1、回溯法解决8皇后问题实验报告算法设计与分析 实验报告 实验名称： 用回溯法解决八皇后问题 姓 名： 学 号： 江 苏 科 技 大 学 一、实验名称：回溯法求解8皇后问题 二、学习知识： 回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解的空间树。算法搜索至解的空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法
2、在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。 三、问题描述 使用回溯法解决八皇后问题。 8皇后问题：在8*8格的棋盘上放置彼此不受攻击的8个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。8后问题等价于在8*8格的棋盘上放置8个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 用高级程序设计语言实现 四、求解思路 Procedure PLACE(k) /如果一个皇后能放在第k行
3、和X(k)列，则返回true，否则返回false。X是一个全程数组，进入此过程时已置入了k个值。ABS(r)过程返回r的绝对值/ global X(1:k); integer i,k; i1 while i0 do / 对所有的行，执行以下语句 / X(k)X(k)+1 /移到下一列/ while X(k)=n and Not PLACE(k) do /此处能放这个皇后吗/ X(k)X(k)+1 /不能放则转到下一列/ repeat if X(k)=n then /找到一个位置/ if k=n then print (X) /是一个完整的解则打印这个数组/ else kk+1;X(k)0 /否
4、则转到下一行/ end if else kk-1 /回溯/ end if repeat End NQUEENS 五、算法实现 本实验程序是使用C#编写，算法实现如下： 1.queen类实现8皇后问题的计算，将结果存入数组。 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; namespace _8Queen public class Queen public static ArrayList arr = new Array
5、List; /存放查询结果 private static bool columflag = new bool8true, true,true,true,true,true,true,true;/列占用标记 true为可用 private static bool leftflag = new bool15true,true,true, true,true,true,true,true,true,true,true,true,true,true,true;/左行对角线占用标记 private static bool rightflag = new bool15true,true, true,tru
6、e,true,true,true,true,true,true,true,true,true,true,true;/右行对角线占用标记 private static int, position = new int,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;/皇后位置坐标 public static int sum = 0; public static void TryStep(int
7、 i)/i取值1至8 for (int j = 1; j = 8; j+) if (columflagj - 1 & leftflagi + j - 2 & rightflagi - j + 7)/如果当前位置可以放置 columflagj - 1 = false; leftflagi + j - 2 = false; rightflagi - j + 7 = false;/占用 positioni - 1, j - 1 = 1;/加入皇后位置 if (i 8) TryStep(i + 1);/进入下一行 else int, position1 = new int8,8;/皇后位置坐标 for
8、 (int m = 0; m 8; m+) /打印解法 for (int n = 0; n 8; n+) position1m, n = positionm, n; arr.Add(position1); int t = arr.Count; sum+;/解法数统计 columflagj - 1 = true;/如果不能放置时，取消占座及移走皇后 leftflagi + j - 2 = true; rightflagi - j + 7 = true; positioni - 1, j - 1 = 0; 2.图形界面 Form1 using System; using System.Collec
9、tions.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; namespace _8Queen public partial class Form1 : Form public Form1 InitializeComponent; run; private PictureBox, card; private int rows;/行数 private int
10、 cols;/列数 private int size = 8; public int index = 0; public int sum; private void run/初始化 动态加载8*8的PictureBox控件，作为棋盘 rows = size; cols = size; this.card = new PictureBoxrows, cols; this.panel1.Controls.Clear; for (int i = 0; i rows; i+) for (int j = 0; j cols; j+) this.cardi, j = new PictureBox; thi
11、s.cardi, j.Location = new System.Drawing.Point(70 * j, 70 * i); this.cardi, j.Name = i.ToString + j.ToString; this.cardi, j.Size = new System.Drawing.Size(70, 70); this.panel1.Controls.Add(cardi, j); Queen.TryStep(1); sum = Queen.arr.Count; for (int f = 1; f = sum; f+) boBox1.Items.Add(f); comboBox1
12、.SelectedIndex = 0; label3.Text = sum.ToString; setPictureBox; public void setPictureBox/布局，放置皇后 int, p = (int,)Queen.arrindex; for (int i = 0; i rows; i+) for (int j = 0; j sum) index = 0; MessageBox.Show(结束！共+sum+种方案?); setPictureBox; comboBox1.Text = (index + 1).ToString; comboBox1.SelectedIndex
13、= index; private void comboBox1_SelectedIndexChanged(object sender, EventArgs e)/选择某一个方案 index = comboBox1.SelectedIndex; setPictureBox; 六、运行结果 任意截取四种方案 共92种方案 可以任选一种方案显示 七、实验小结： 回溯法有“通用解题法”之称。用它可以系统地搜索一个问题的所有解或任一解。回溯法在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先策略搜索。它适合于解组合数较大的问题 程序下载地址：
