四． 代码与注解：
#include <math.h>
#include <stdio.h>
#include<string.h>
#include<conio.h> //用getch()要调用的头文件
#include <stdlib.h> //要用system函数要调用的头文件
int SUM=0; //统计有多少种可能
int shezhi(){ //设置为N皇后问题
}
void Print(int N,int x[]) //印出結果
{
int MAX=N;
for(int i=0;i<MAX;i++)
{ for(int j=0;j<MAX;j++) if(j==x[i]) printf("●"); else printf("○"); int N; printf("这是一个N皇后问题...\n请输入N="); scanf("%d",&N); return N; printf("\n"); } SUM++; //打印一种情况统计一次
printf("\n");
}
int Judge(int k,int x[]) //判断是否在同一直、橫、斜线上有其它棋子 {
int i;
for(i=0;i<k;i++)
if( abs(k-i)==abs(x[i]-x[k]) || x[i]==x[k] ) //函数名: abs; 功能: 求整数的绝对值 ;
return 0;
return 1;
}
void backtrack(int t,int N,int x[]) // 把棋子放到棋盘上
{ int MAX=N;
int i;
for(i=0;i<MAX;i++){
x[t]=i;
if(Judge(t,x))
{
if(t==MAX-1){
Print(MAX,x); // 找到其中一种放法，印出結果
} }
} else backtrack(t+1,N,x);
}
void Introduce(){
printf("* * * * * * * * * * * * * * * * * *\n"); printf("* 数据结构课程设计 *\n"); printf("* *\n"); printf("* 组员：尹佐斌 黄文毅 *\n"); printf("* 檀卫杰 马赈耀 *\n"); printf("* *\n");
printf("* * * * * * * * * * * * * * * * * *\n"); printf("\n\n"); printf("1.设置为N皇后问题。\n"); printf("2.输出棋局排布结果。\n"); printf("3.统计棋局排布总数。\n"); printf("4.清屏。\n");
printf("\n\n");
}
void main()
{ int N;
int x[10];
printf("\n\n\n");
char flag=1;
while(flag){ int n; Introduce(); char a; printf("您确定要进行上述操作吗?(Y/N):"); a=getchar(); while(a=='Y'||a=='y'){ printf("请选择：");
scanf("%d",&n); switch(n){ case 1: N=shezhi(); break; case 2: backtrack(0,N,x); printf("按任意键返回..."); getch(); system("cls"); Introduce(); break; case 3: printf("统计结果:%d\n",SUM); printf("按任意键返回..."); getch(); system("cls"); Introduce(); break; case 4:
printf("按任意键返回..."); getch(); system("cls"); Introduce(); break; default: printf("输入错误...\n"); } } printf("按任意键返回..."); getch(); system("cls"); Introduce(); break;
}
}
第二篇：c++利用栈解决八皇后问题_数据结构实验报告
XX级数据结构实验报告
实验名称： 实验二——栈和队列
学生姓名：
班 级：
班内序号：01
学 号：
1．实验要求
【实验目的】
1、 进一步掌握指针、模板类、异常处理的使用
2、 掌握栈的操作的实现方法
3、 掌握队列的操作的实现方法
4、 学习使用栈解决实际问题的能力
5、 学习使用队列解决实际问题的能力
【实验内容】
利用栈结构实现八皇后问题。
八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。
提示：
1、可以使用递归或非递归两种方法实现
2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上
2. 程序分析
2.1 存储结构
存储结构：栈（递归）
2.2 关键算法分析
【设计思想】
由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法
【伪代码】
1、 输入皇后个数n
2、 k=1
3、 判断k是否大于n
3.1 是：打印一组可能
3.2 否：循环行位置1~n
判断该位置是否符合要求，若符合记录q[k]的坐标y值
k+1 重复3
【关键算法】
1、递归
void Queen::queen(int n) //递归函数的具体定义
{
if(n==Number+1) //如果一到八行都已安排了皇后，则输出皇后位置
{Print();return;}
for(int i=1;i＜=Number;i++) //从行号n=1开始逐个试探，即从i=1列开始
{Site[n]=i;
if(IsValid(n)) //如果第n行可以取第i列上的位置，则开始试探第n+1行
{queen(n+1);}
int Queen::IsValid(int n) //判定位置函数的具体定义，当皇后位于第n行时
{for(int m=1;m
{if(Site[m]==Site[n]) return 0; //当m行与n行皇后位于同一列时，不符合要求，返回0
if(abs(Site[m]-Site[n])==abs(m-n)) return 0; //当m行与n行皇后位于同一对角线时，不符合要求，返回0
}return 1; //第n行皇后位置符合要求，返回1
};
void Queen::Print() //输出函数的具体定义
{count++; //解法的号数
for(int i=1;i＜=Number;i++)
{cout＜＜"("＜
cout＜＜"No."＜
};
2.3 其他
源代码：
时间复杂度：O(n)
#include
#include
using namespace std;
#define N 10
class Queen
{
public:
Queen(){num=-1;}
void Print(int n);//输出皇后的排列，打出的数字为每个皇后的坐标
int Check(int i,int k);//判断位置是否符合要求
void Queens(int k,int n);//递归调用
int count();//计数
private:
int q[N];
int num;
};
void main()
{
Queen Q;
int n;
cout＜＜"请输入Queen的数目(n＞0):"＜
cin＞＞n;
if(n＞0)
{
cout＜＜"Queen可能的位置坐标:"＜
Q.Queens(1,n);
cout＜＜"共有 "＜
}
else
cout＜＜"ERROR输入数字错误"＜
}
void Queen::Queens(int k,int n)//计算出皇后的排列，k是当前皇后数量，n是数量上限
{ int i;
if(k＞n)//如果达到里要求的数量输出皇后排列
{ Print(n);
count();
}
else //否则在适当的位置添加一个新皇后
{
for(i=1;i＜=n;i++)
if(Check(i,k)) //判断该行中该位置放置'皇后'是否符合要求
{
q[k]=i; //记录改行中该点的位置
Queens(k+1,n); //放置下一行的'皇后'
}
}
}
void Queen::Print(int n)
{
int i;
for(i=1;i＜=n;i++)
cout＜＜"("＜
cout＜
}
int Queen::Check(int i,int k)
{
int j;
j=1;
while(j
{
if((q[j]==i) || abs(q[j]-i)==abs(j-k)) //判断列，判断斜线
return 0; //不符合返回0
j++;
}
return 1; //符合返回
}
int Queen::count()
{
num++;
return num;
}
3. 程序运行结果
（1）测试主函数流程
（2）测试条件
n取值大于0小于10
本题中一般取n=8
（3）测试结论
测试正常，如图
4. 总结