XX 学院计算机与信息工程学院
算
法
设
计
报
告
年 月 日
课程名称
算法分析
项目名称
求解 n 皇后问题
班 级
学 号
姓 名
指导教师
第一题： 求解 n 皇后问题
一、 算法问题描述
在 n×n 的方格棋盘上，放置 n 个皇后，要求每个皇后不同行、不同列、不同左
右对角线。
分别使用
1、递归算法
2、回溯法利用栈
3、回溯法不利用栈
二、 算法问题形式化表示
例如：求解 4 皇后问题
放第 1 个皇后
三、 期望输入与输出
输入：数字
输出：n 皇后问题的求解结果
四、 算法分析与步骤描述
1、递归算法求解 n 皇后问题
问题求解：采用整数数组去 q[N]存放 n 皇后问题的求解结果，因为每行只
能放一个皇后，去 q[i](1<=i<=n)的值表示第 i 个皇后所在的列号，即该皇后放
在（i,q[i]）的位置上。
对于（k,j）位置上的皇后，是否与已放好的皇后（i,q[i]）(1<=i<=k-1)有
×
×
放第 2 个皇后
×
×
×
第 3 个皇后放不下，回
溯到第 2 个皇后，找其
下一个位置
×
×
×
×
放第 3 个皇后
×
×
×
×
放第 2 个皇后
×
×
×
×
放第 3 个皇后
×
×
×
×
×
×
×
×
放第 4 个 n 皇后
×
×
第 4 个皇后放不下，回溯到第
3 个皇后，没有合适的位置，
回溯到第 2 个皇后，也没有合
适的位置，回溯到第 1 个皇后，
找下一个位置
