C N皇后问题(含源码)
- 格式：pdf
- 大小：302.92 KB
- 文档页数：8
int i; for(i=1;i<=n;i++) row[i]=false; //表示所有行都没有放皇后 for(i=1;i<2*n;i++) diag[i]=false; //所有对角线没有放皇后 for(i=1;i<2*n;i++) backdiag[i]=false; //所有反对角线没有放皇后 in.close(); //关闭文件 }
试验中，我们按照从简单到复杂的方法，一步一个脚印编写代码，使得程序不易发 生错误，并且容易更正，编写出来的程序代码简洁明朗，效率较高；
通过对例题的学习，我们最终将正确的代码编写出，并在不断地修改之下做到方便 用户使用的要求；
编码的速度有一个从慢到快的过程，在本次试验中，我们的速度依然比较慢，这看 出我们平时编码比较少，缺乏熟练度，并对算法了解不深入；
cout<<"打开文件 output.txt 失败"<<endl; exit(2); } outfile<<"第"<<++num<<"个解："; outfile<<"("<<x[1]; for(int i=2;i<=n;i++) outfile<<","<<x[i]; outfile<<")"<<endl; outfile.close(); }
ofstream outfile("output.txt",ios::app);
中输入 ios：：app，同时，我们的递归算法有一处写错了代码，这样的粗心导致无法得到 结果。
实验中，我采用的是文件夹输入输出，所以在运行过程中，dos 窗口中不会出现数 据，但在这个时候，程序已经在 input.txt 中读取数据，将皇后问题计算出，并把结 果输出到 output.txt 中。
在 input.txt 中，输入任意一个数字，运行程序，即可在 output.txt 中得到相 应的结果：
否则
在此处放置 皇后，并保 存解为（r，c）
当放置的皇后数 等于行列数 （c+1>n）时，调 用 output 函数
递归算法中，首先定义三个 bool 型变量，分别表示行，对角线，反对角线是否有 皇后，若有，则用 true 表示出来。用循环，依次求出满足要求的点，如果满足，则放 置皇后，然后循环查找能放置下一个皇后的点。当放置的皇后数目等于行列数时，就调 用函数将结果输出。
output.txt 文件
—————————————————————————————————————— 2、实验准备工作（阐述解决问题所涉及的算法思想，至少要画一个算法流程图来说明） 本实验采用递归算法：
第 c 皇后（c=1）
第 c+1 个皇后
行 r 进行循 环查找
若（r.c）所在行， 对角线，反对角 线无皇后
queen::~queen() {
delete []row; delete []diag; delete []backdiag; delete []x; }
#endif
#include"queen.h"
main.cpp 文件：
int maLeabharlann n() {queen objqueen; objqueen.run(); system("PAUSE"); return 0; } —————————————————————————————————————— 3、实验现象及结论（应用文字和程序运行的截图说明程序测试现象，并解释结果）
当输入 7 时，共有 40 个解，结果截图如下：
当输入 8 时，共有 92 个解，部分截图如下：
当输入 10 时，部分解的截图如下：
—————————————————————————————————————— 4、实验总结（是否成功解决问题，总结实验中最有价值的内容，程序能够在哪些方面进
一步改善，自我评价成败得失）
backtracking(1); }
};
queen::queen() {
ifstream in("input.txt",ios::in); if(!in) //当打开失败时 {
cout<<"打开文件 input.txt 失败！"<<endl; exit(1); } int num; in>>num; //再文本文件中读取一个数字 num n=num; //令 n=num row=new bool[n+1]; //分配行所占空间 diag=new bool[2*n]; //分配对角线所占空间 backdiag=new bool[2*n]; //分配反对角线所占空间 x=new int[n+1]; //解所占空间
void queen::output() {
static int num=0; //表示当前已经求得的解个数 ofstream outfile("output.txt",ios::app); //不写 ios::app 默认是以 ios::out 打开，只能得到最后一个解。 if(!outfile) {
一、 实验设计方案
1、实验内容与目的（简单介绍实验内容，说明实验目的） 实验目的：要求在一个 n*n 的棋盘上放置 n 个皇后，要求放置的 n 个皇后不会互相
吃掉；皇后棋子可以吃掉它所在的那一行、那一列，以及那两条对角线上的任何棋子。 实验内容：你的具体选择（要详细） 通 过 input.txt 文 件 输 入 一 个 数 字 n ， 求 出 n 皇 后 问 题 ， 并 将 结 果 输 出 到
class queen //定义一个 queen 类 { private:
int n; //需要解决的 n 皇后问题 bool *row; //行是否有皇后 bool *diag; //对角线是否有皇后 bool *backdiag; //反对角线是否有皇后 int *x; //皇后问题的解
void backtracking(int c); //用于递归求解的函数 void output(); //文件输出函数 public: queen(); //构造函数 virtual~queen(); //析构函数 void run() //用于执行递归求解，并计算出所有皇后问题的解 {
但是我们的代码看起来仍然有些凌乱，效率还没有带到真正的高效，每次运行都需 要等待几秒钟。再以后我们将通过练习基础功，简化程序代码，实现简单代码完善功能 的理想。
在编辑过程中，开始我们编写出的程序能够通过编译，但不能通过文件输出结果， output.txt 中始终都没有结果出现，通过反复的调试，仍然没有找到原因，因此请教了其 他同学，在其他同学的帮助下，我们发现我们的错误在于没有在
void queen::backtracking(int c) {
if(c>n) output(); //当放置的皇后数等于行数时，输出结果 else {
for(int r=1;r<=n;r++) //行循环 {
if(!row[r] && !diag[n-c+r] && !backdiag[r+c-1]) //当（r，c）所在行，对角线，反对角线都没有放置皇后时 {
row[r]=diag[n-c+r]=backdiag[r+c-1]=true; //这点合符要求，在此处放置皇后 x[c]=r;
//解为（r，c） backtracking(c+1); //c 加一，继续放置下一个皇后 row[r]=diag[n-c+r]=backdiag[r+c-1]=false; //清空操作 } } } }
——————————————————————————————————————
二、实验步骤、测试与结果分析
1、源程序的设计（在此附上源程序（cpp 文件）清单）
queen.h 文件：
#ifndef __QUEEN_H__ #define __QUEEN_H__ #include<iostream> #include<fstream> //文件流 using namespace std;
试验中，我们按照从简单到复杂的方法，一步一个脚印编写代码，使得程序不易发 生错误，并且容易更正，编写出来的程序代码简洁明朗，效率较高；
通过对例题的学习，我们最终将正确的代码编写出，并在不断地修改之下做到方便 用户使用的要求；
编码的速度有一个从慢到快的过程，在本次试验中，我们的速度依然比较慢，这看 出我们平时编码比较少，缺乏熟练度，并对算法了解不深入；
cout<<"打开文件 output.txt 失败"<<endl; exit(2); } outfile<<"第"<<++num<<"个解："; outfile<<"("<<x[1]; for(int i=2;i<=n;i++) outfile<<","<<x[i]; outfile<<")"<<endl; outfile.close(); }
ofstream outfile("output.txt",ios::app);
中输入 ios：：app，同时，我们的递归算法有一处写错了代码，这样的粗心导致无法得到 结果。
实验中，我采用的是文件夹输入输出，所以在运行过程中，dos 窗口中不会出现数 据，但在这个时候，程序已经在 input.txt 中读取数据，将皇后问题计算出，并把结 果输出到 output.txt 中。
在 input.txt 中，输入任意一个数字，运行程序，即可在 output.txt 中得到相 应的结果：
否则
在此处放置 皇后，并保 存解为（r，c）
当放置的皇后数 等于行列数 （c+1>n）时，调 用 output 函数
递归算法中，首先定义三个 bool 型变量，分别表示行，对角线，反对角线是否有 皇后，若有，则用 true 表示出来。用循环，依次求出满足要求的点，如果满足，则放 置皇后，然后循环查找能放置下一个皇后的点。当放置的皇后数目等于行列数时，就调 用函数将结果输出。
output.txt 文件
—————————————————————————————————————— 2、实验准备工作（阐述解决问题所涉及的算法思想，至少要画一个算法流程图来说明） 本实验采用递归算法：
第 c 皇后（c=1）
第 c+1 个皇后
行 r 进行循 环查找
若（r.c）所在行， 对角线，反对角 线无皇后
queen::~queen() {
delete []row; delete []diag; delete []backdiag; delete []x; }
#endif
#include"queen.h"
main.cpp 文件：
int maLeabharlann n() {queen objqueen; objqueen.run(); system("PAUSE"); return 0; } —————————————————————————————————————— 3、实验现象及结论（应用文字和程序运行的截图说明程序测试现象，并解释结果）
当输入 7 时，共有 40 个解，结果截图如下：
当输入 8 时，共有 92 个解，部分截图如下：
当输入 10 时，部分解的截图如下：
—————————————————————————————————————— 4、实验总结（是否成功解决问题，总结实验中最有价值的内容，程序能够在哪些方面进
一步改善，自我评价成败得失）
backtracking(1); }
};
queen::queen() {
ifstream in("input.txt",ios::in); if(!in) //当打开失败时 {
cout<<"打开文件 input.txt 失败！"<<endl; exit(1); } int num; in>>num; //再文本文件中读取一个数字 num n=num; //令 n=num row=new bool[n+1]; //分配行所占空间 diag=new bool[2*n]; //分配对角线所占空间 backdiag=new bool[2*n]; //分配反对角线所占空间 x=new int[n+1]; //解所占空间
void queen::output() {
static int num=0; //表示当前已经求得的解个数 ofstream outfile("output.txt",ios::app); //不写 ios::app 默认是以 ios::out 打开，只能得到最后一个解。 if(!outfile) {
一、 实验设计方案
1、实验内容与目的（简单介绍实验内容，说明实验目的） 实验目的：要求在一个 n*n 的棋盘上放置 n 个皇后，要求放置的 n 个皇后不会互相
吃掉；皇后棋子可以吃掉它所在的那一行、那一列，以及那两条对角线上的任何棋子。 实验内容：你的具体选择（要详细） 通 过 input.txt 文 件 输 入 一 个 数 字 n ， 求 出 n 皇 后 问 题 ， 并 将 结 果 输 出 到
class queen //定义一个 queen 类 { private:
int n; //需要解决的 n 皇后问题 bool *row; //行是否有皇后 bool *diag; //对角线是否有皇后 bool *backdiag; //反对角线是否有皇后 int *x; //皇后问题的解
void backtracking(int c); //用于递归求解的函数 void output(); //文件输出函数 public: queen(); //构造函数 virtual~queen(); //析构函数 void run() //用于执行递归求解，并计算出所有皇后问题的解 {
但是我们的代码看起来仍然有些凌乱，效率还没有带到真正的高效，每次运行都需 要等待几秒钟。再以后我们将通过练习基础功，简化程序代码，实现简单代码完善功能 的理想。
在编辑过程中，开始我们编写出的程序能够通过编译，但不能通过文件输出结果， output.txt 中始终都没有结果出现，通过反复的调试，仍然没有找到原因，因此请教了其 他同学，在其他同学的帮助下，我们发现我们的错误在于没有在
void queen::backtracking(int c) {
if(c>n) output(); //当放置的皇后数等于行数时，输出结果 else {
for(int r=1;r<=n;r++) //行循环 {
if(!row[r] && !diag[n-c+r] && !backdiag[r+c-1]) //当（r，c）所在行，对角线，反对角线都没有放置皇后时 {
row[r]=diag[n-c+r]=backdiag[r+c-1]=true; //这点合符要求，在此处放置皇后 x[c]=r;
//解为（r，c） backtracking(c+1); //c 加一，继续放置下一个皇后 row[r]=diag[n-c+r]=backdiag[r+c-1]=false; //清空操作 } } } }
——————————————————————————————————————
二、实验步骤、测试与结果分析
1、源程序的设计（在此附上源程序（cpp 文件）清单）
queen.h 文件：
#ifndef __QUEEN_H__ #define __QUEEN_H__ #include<iostream> #include<fstream> //文件流 using namespace std;
