C++课程设计实践报告书-八皇后问题.doc

课程设计报告

设计题目：对八皇后问题进行求解
学生姓名：
专 业：计算机科学与技术
班 级：09-2
学 号：
指导教师：李俊照
完成日期：2010-5-30
合肥工业大学计算机与信息学院

（一） 需求和规格说明
在8行8列的棋盘上放置8个皇后，使任一个皇后都不能吃掉其他的7个皇后（注：皇后可吃掉与她处于同行或同列或同一对角线上的其他棋子），并将结果以某种方式显示出来。
例如，当求出下述的一个解时，可输出如下信息来表示该解（输出了表示摆放皇后的坐标位置以及“棋盘状态”— 棋盘中有皇后的位置放一个“Q”字符，其他位置为“+”字符）。
(1,1) (5,2) (8,3) (6,4) (3,5) (7,6) (2,7) (4,8)
Q + + + + + + +
+ + + + + + Q +
+ + + + Q + + +
+ + + + + + + Q
+ Q + + + + + +
+ + + Q + + + +
+ + + + + Q + +
+ + Q + + + + +
（二） 设计
（1） 通过“int LineNum[9]; bool a[9], b[15], c[15];”说明具有全局作用域的4个数组。其中的：
LineNum[i]表示第i列的皇后要放的行位置（只用其中的列号1到8）；
a[i]为true（i =1，2，…，8）表示第i行上尚未放皇后；
b[i]为true（i =0，1，2，…，14）表示第i条斜对角线上尚未放皇后（斜对角线指的是“/”状对角线，该对角线上各点的行列号之和i+j为一个常数）；
c[i]为true（i=0，1，2，…，14）表示第i条反斜对角线上尚未放皇后（反斜对角线指的是“\”状对角线，该对角线上各点的行列号之差i-j为一个常数）。
从而当使用语句“if ( a[j] && b[i+j-2] && c[i-j+7] ) LineNum[i]=j;”时，可用于判断并实现：如果在第j行的第i列上放置皇后安全的话，则将一枚皇后放置到那儿。
（2）编制一个具有如下原型的递归函数solve，它负责往第i列开始的连续8-i+1列上均放上皇后，若成功则通过引用参数ok返回true（否则返回false）。
void solve(int i, bool& ok);
摆放皇后之后，若i=8即已放满时则递归出口；否则通过solve(i+1,ok);进行递归调用。
（3）编制主函数，首先初始化一个“空棋盘”，即将a、b、c数组的各元素均置为true（表示当前棋盘的8个行、15条斜对角线以及15条反斜对角线上都尚未摆放皇后）。而后执行调用语句“solve(1, ok);”，它负责往第1列开始的连续8列上均放上皇后，若成功则通过引用参数ok返回true（否则返回false）。
（三） 用户手册
直接运行即可
（四） 调试及测试
运行实例：
Q + + + + + + +
+ + + + + + Q +
+ + + + Q + + +
+ + + + + + + Q
+ Q + + + + + +
+ + + Q + + + +
+ + + + + Q + +
+ + Q + + + + +
进一步改进：
（1）可改用非递归方法设计并编写solve函数，那样的话，通常要设置数组来记录皇后的摆放位置信息，还要记录这些皇后所产生的“影响面”（所建立的“势力范围”）— 使得哪些行列位置不可再摆放皇后。当在新的行列位置摆放了皇后、但此时又无法进一步摆放其他的皇后时，要回退（回溯）到上一个位置接着去考虑另外的“行走”方法（若还有的话）等等。但注意，“回退”一步后，要同时“撤销”由于该步的回退而关联的那些“影响面”（释放“势力范围”）。
（2）本程序只是找到了某一种“摆放方案”而终止，还可进一步考虑寻找其他各种不同的“摆放方案”（实际上共有92种）。
（3）也可用同样的方法去处理其他“阶数”的皇后问题，如求解四皇后问题等。
附录：源程序
#include <iostream>
#include <cmath>
using namespace std;
int LineNum[9];
bool a[9], b[15], c[15];
void solve(int i, bool& ok);
void Output();
void main()
{
bool ok;
int i;
ok=false;
for(i = 1 ; i <=8 ; i++)
{
a[i]=true;
}
for(i = 0 ; i <=14 ; i++)
{
b[i]=true;
c[i]=true;
}
solve (1,ok);
}
void solve(int i, bool& ok)
{
int j;
if(i == 9 ||ok==true)
{
ok=true;
Output();
return;
}
for(j = 1 ; j<= 8 ; j++)
{
if ( a[j] && b[i+j-2] && c[7+i-j] )
{
LineNum[i]=j;
a[j]=false;
b[i+j-2]=false;
c[7+i-j]=false;
solve (i+1,ok);
if(ok==false)
{
a[j]=true;
b[i+j-2]=true;
c[7+i-j]= true;
}
}
}
}
void Output()
{
int i,j;
for(i = 1 ; i < 9 ; i++)
cout<<" "<<"("<<LineNum[i]<<","<<i<<")";
cout<<endl;
for(j = 1 ; j < 9 ; j++)
{
for(i=1;i<9;i++)
{
if (LineNum[i]==j)
cout<<"Q";
else
cout<<"+";
cout<<" ";
}
cout<<endl;
}
}