算法设计与分析
实验报告
实验名称： 用回溯法解决八皇后问题
姓 名：
学 号：
江 苏 科 技 大 学
一、实验名称：回溯法求解 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;
i1
while i<k do
if X(i)=X(k) or ABS(X(i)-X(k))=ABS(i-k) then
return (false)
end if
ii+1
repeat
return (true)
End PLACE
Procedure NQUEENS(n)
//此过程使用回溯法求出一个 n*n 棋盘上放置 n 个皇后，使其不能互相攻击的所有可
能位置//
integer k,n,X(1:n)
X(1)0 ; k1 // 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 kk+1;X(k)0 //否则转到下一行//
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 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},
