文档介绍：人工智能
课程设计报告

题目：八皇后问题
班级：
姓名：
学号：
电话：
信息科学与工程学院人工智能课程设计八皇后问题

目录

(一) 问题提出..................................2
(二) 基本思路..................................2
(三) 解决方案..................................4
(四) 状态表示的数据结构........................4
(五) 算法流程..................................5
(六) 搜索产生的状态空间图......................6
(七) OPEN 表和 CLOSE 表变化过程..................8
(八) 程序清单....................... ......... .8
(九) 实验结果讨论..............................11

1
信息科学与工程学院人工智能课程设计八皇后问题

(一) 问题提出
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十
九世纪著名的数学家高斯 1850 年提出。
在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或
同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯
提出了一个问题：在 8*8 的格的国际象棋上摆放八个皇后，使其不能相互攻击，
即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种
解法。

(二) 基本思路
采用深度优先算法，即回溯法解决八皇后问题。回溯法不是按照某种公式或
确定的法则,求问题的解,而是通过试探和纠正错误的策略,找到问题的解.
这种方法一般是从一个原始状态出发,通过若干步试探,最后达到目标状态
终止。
回溯法在理论上来说,就是在一棵搜索树中从根结点出发,找到一条达到满
,对于每一个中间结点,他的位置以及向
下搜索过程是相似的,因此完全可以用递归来处理。

2
信息科学与工程学院人工智能课程设计八皇后问题

有界深度优先搜索算法框图（在八皇后问题中深度为 8）
起始
把 s 放入 open 表
是
是否为目标节点？
S 成功