回溯法解决8皇后问题实验报告

算法设计与分析实验报告实验名称： 用回溯法解决八皇后问题 姓 名： 学 号： 江 苏 科 技 大 学一、实验名称：回溯法求解8皇后问题二、学习知识：回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解的空间树。算法搜索至解的空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。三、问题描述（1）使用回溯法解决八皇后问题。8皇后问题：在8*8格的棋盘上放置彼此不受攻击的8个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。8后问题等价于在8*8格的棋盘上放置8个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。（2）用高级程序设计语言实现四、求解思路Procedure PLACE(k)/如果一个皇后能放在第k行和X(k)列，则返回true，否则返回false。X是一个全程数组，进入此过程时已置入了k个值。ABS(r)过程返回r的绝对值/global X(1:k); integer i,k;i1while i0 do / 对所有的行，执行以下语句 /X(k)X(k)+1 /移到下一列/while X(k)=n and Not PLACE(k) do /此处能放这个皇后吗/X(k)X(k)+1 /不能放则转到下一列/repeatif X(k)=n then /找到一个位置/ if k=n then print (X) /是一个完整的解则打印这个数组/else kk+1;X(k)0 /否则转到下一行/ end if else kk-1 /回溯/end ifrepeatEnd 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 ArrayList(); /存放查询结果 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,true,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 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 (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.图形界面 Form1using System;using System.Collections.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 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(); this.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.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 = index; private void comboBox1_SelectedIndexChanged(object sender, EventArgs e)/选择某一个方案 index = comboBox1.SelectedIndex; setPictureBox(); 六、运行结果任意截取四种方案 共92种方案 可以任选一种方案显示 七、实验小结：回溯法有“通用解题法”之称。用它可以系统地搜