回溯法解决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; 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

本文来源：https://www.bwwdw.com/article/6im5.html