回溯法解决8皇后问题实验报告
更新时间:2024-02-28 04:45:01 阅读量: 综合文库 文档下载
算法设计与分析
实验报告
实验名称: 用回溯法解决八皇后问题 姓 名: 学 号:
江 苏 科 技 大 学
一、实验名称:回溯法求解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; i?1
while i if X(i)=X(k) or ABS(X(i)-X(k))=ABS(i-k) then return (false) end if i?i+1 repeat return (true) End PLACE Procedure NQUEENS(n) //此过程使用回溯法求出一个n*n棋盘上放置n个皇后,使其不能互相攻击的所有可能位置// integer k,n,X(1:n) X(1)?0 ; k?1 // k是当前行;X(k)是当前列 // while k>0 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 k?k+1;X(k)?0 //否则转到下一行// end if else k?k-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 ArrayList(); //存放查询结果 private static bool[] columflag = new bool[8]{true, true,true,true,true,true,true,true};//列占用标记 true为可用 private static bool[] leftflag = new bool[15]{true,true,true, true,true,true,true,true,true,true,true,true,true,true,true};//左行对角线占用标记 private static bool[] rightflag = new bool[15]{true,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 (columflag[j - 1] && leftflag[i + j - 2] && rightflag[i - j + 7])//如果当前位置可以放置 { columflag[j - 1] = false; leftflag[i + j - 2] = false; rightflag[i - j + 7] = false;//占用 position[i - 1, j - 1] = 1;//加入皇后位置 if (i < 8) TryStep(i + 1);//进入下一行 else { int[,] position1 = new int[8,8];//皇后位置坐标à for (int m = 0; m < 8; m++) //打印解法 { for (int n = 0; n < 8; n++) position1[m, n] = position[m, n]; } arr.Add(position1); int t = arr.Count; sum++;//解法数统计 } columflag[j - 1] = true;//如果不能放置时,取消占座及移走皇后 leftflag[i + j - 2] = true; rightflag[i - j + 7] = true; position[i - 1, j - 1] = 0; } } } } } 2.图形界面 Form1 using 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 PictureBox[rows, cols]; this.panel1.Controls.Clear(); for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { this.card[i, j] = new PictureBox(); this.card[i, j].Location = new System.Drawing.Point(70 * j, 70 * i); this.card[i, j].Name = i.ToString() + j.ToString(); this.card[i, j].Size = new System.Drawing.Size(70, 70); this.panel1.Controls.Add(card[i, j]); } } Queen.TryStep(1); sum = Queen.arr.Count; for (int f = 1; f <= sum; f++) { this.comboBox1.Items.Add(f); } comboBox1.SelectedIndex = 0; label3.Text = sum.ToString(); setPictureBox(); } public void setPictureBox()//布局,放置皇后 { int[,] p = (int[,])Queen.arr[index]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (((i % 2) != (j % 2))) { if (p[i, j] == 0) this.card[i, j].Image = Image.FromFile(\背景\\\\3.jpg\); else this.card[i, j].Image = Image.FromFile(\背景\\\\1.jpg\); } else { if (p[i, j] == 0) this.card[i, j].Image = Image.FromFile(\背景\\\\4.jpg\); else this.card[i, j].Image = Image.FromFile(\背景\\\\2.jpg\); } } } } private void next_Click(object sender, EventArgs e)//点击“下一个”按钮 { index++; if (index+1 > 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种方案 可以任选一种方案显示 七、实验小结: 回溯法有“通用解题法”之称。用它可以系统地搜索一个问题的所有解或任一解。回溯法在问题的解空间树中,按深度优先策略,从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先策略搜索。它适合于解组合数较大的问题 程序下载地址:http://download.csdn.net/detail/orchid_0606/8347899
正在阅读:
回溯法解决8皇后问题实验报告02-28
公司债券承销业务尽职调查专项指引梳理10-20
八年级第一学期期末考试试卷06-11
配送线路优化的方法-节约里程法01-31
安徽公务员考试《行测》通关模拟试题及答案解析【2022】:14 604-13
手机保护膜钢化璃玻膜检验标准(最全版)05-09
中国啤酒产业发展现状与盈利空间研究报告(2014-2019)04-29
循环小数案例04-05
新纲P1-109CMA习题01-14
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 回溯
- 皇后
- 实验
- 解决
- 报告
- 问题
- 2009 - 10 - 1微机原理试题A卷 - 图文
- 07模电试卷A
- 计本 iPhone手机应用开发设计(爱炒股) - 图文
- 物理性污染控制习题答案解析第三章
- 免费留学 GMAT考后经验分享
- 《法律基础》课中案例教学法探讨
- 论文- 副本
- 金融工程的期末练习题附参考答案
- 中国近年桥梁坍塌事故一览(图)
- 如何给你未来的研究生导师写邮件
- 电动汽车充电桩建设项目可行性研究报告
- 技能比武大赛理论考试题库
- XX公司管理系统境外工程突发事件应急预案的
- 价格理论与实务说课稿
- 《面向对象程序设计》课程设计 教学大纲
- 围护专项施工方案(SMW工法桩,609钢管支撑,坑内外搅拌桩加固)
- 大学生人际交往与心理健康课件
- 塔吊安全施工方案
- 中山市实验小学体育馆项目工程技术标 - 图文
- 现代视角下中希神话女性悲剧比较