一道题目.......
今天老师让我做一道那什么八皇后的题目.......没啥思路，请问谁做过，给提个醒........... 问题点数：15、回复次数：8Top
1 楼llf_hust（）回复于 2005-04-21 22:39:40 得分 0
程序员考试的书上有这道题的答案和分析Top
2 楼wy198796（吴胤）回复于 2005-04-21 23:19:30 得分 0
我想自己做~那样比较有意思~不过有点找不到入口~................Top
3 楼SaiRose（Learning......）回复于 2005-04-22 08:53:28 得分 0
递归，回朔Top
4 楼zhousqy（标准C匪徒)(甩拉，甩拉）回复于 2005-04-22 10:36:26 得分 0
軟考書上有的。Top
5 楼venusluna（李萌）回复于 2005-04-22 19:40:15 得分 5
在一个8*8的棋盘上放置8个皇后，使得两两不在一条横or竖or斜线上。你可以想象使第一个棋子占据第一行棋盘的第一个位置(1,1)，然后将第二个棋子置于第二行棋盘的满足皇后间条件的位置，比如(2,3),依次逐行两两判断。遇到没有位置可放的情况自然要将前面一行的棋子位置继续移动一个，也就是要回溯，其余的细节你可以参考一下相关书籍，可以递归当然也可以用非递归实现。希望我说得还算清晰哦:)Top
6 楼ouyangdongfang（菜鸟之小猪笨笨）回复于 2005-04-22 20:55:33 得分 10
最好使用栈来解决这个问题：
1，先建立一个栈,然后就是像楼上说的那样,先把第一个棋子放入第一行，第一列(1,1)，把它存入栈底。
2，遍历找第二个棋子的位置,将第二个棋子置于第二行棋盘的满足条件的位置，比如(2,3),再存入栈顶。
3，寻找第三个棋子得位置，
4，…………
5，在遍历完寻找不到该棋子得位置时，就是上一个棋子放的位置不对。将上一个棋子出栈，再遍历寻找上一个棋子的其他位置，
6，如果还找不到就是上一个的上一个的棋子的位置不对，再继续出栈， 遍历寻找其位置，
7，……
其实就是一个递归，回朔的问题，只是在递归，回溯的过程中，使用栈来存放所找到棋子的位置。
不知道我有没有说得清楚，希望我的还能楼主理解一下哈！:)Top
7 楼wy198796（吴胤）回复于 2005-04-22 22:54:23 得分 0
谢谢各位前辈啦~~~小弟学了刚20天C语言......昨天上课我做完所有题目，老师出我道这题目，晕死我了~~~Top
8 楼Yuna_2z（其实游戏是一艺术,而我只是身陷其中！）回复于 2005-04-29 16:03:39 得分 0
给你一个N皇后问题的代码~~`
、//演示程序十九：ｎ个皇后问题
#include<iostream.h>
#include<stdlib.h>
/*
在 n 行 n 列的国际象棋棋盘上，最多可布n个皇后。
若两个皇后位于同一行、同一列、同一对角线上，
则称为它们为互相攻击。
n皇后问题是指找到这 n 个皇后的互不攻击的布局。
n 行 n 列的棋盘上，主次对角线各有2n-1条。
利用行号i和列号j计算
主对角线编号k的方法是k = n+i-j-1；
计算次对角线编号k的方法是k = i+j
*/
//"ｎ个皇后问题"之类定义
class Queen {
private:
int n; //皇后问题的大小
int *col; //数组，各列上有无皇后(0，1)
int *md; //数组，各主对角线有无皇后(0，1)
int *sd; //数组，各次对角线有无皇后(0，1)
int *q; //数组，第i行上皇后在第几列(0,n-1)
int Q; //已布皇后数，计数
int r; //ｎ皇后问题的解的组数
public:
Queen(int); //构造函数
~Queen();
void showBoard(); //函数：打印棋盘
void resolve(int); //求解n皇后问题
void HowMany(); //输出解的个数
};
//构造函数:参数缺省为5皇后问题
Queen::Queen(int x=5)
{ //动态数组分配:请注意new运算符的语法。
//new int[n]方括号内数组长度。
//a=new int(12)，圆括号内单变量的初值。
n=x;Q=0;r=0;
col=new int[n]; if(!col) exit(0);
md=new int[2*n-1]; if(!md) exit(0);
sd=new int[2*n-1]; if(!sd) exit(0);
q=new int[n]; if(!q) exit(0);
int i;
//动态分配的数组初值不确定，要赋0
for(i=0;i<n;i++) col[i]=q[i]=0;
for(i=0;i<2*n-1;i++) md[i]=sd[i]=0;
}
//析购
Queen::~Queen()
{
delete []col;delete []md;
delete []sd;delete []q;
}
//函数：打印棋盘
void Queen::showBoard()
{
int i,j;
for(i=0;i<n;i++) {
for(j=0;j<n;j++)
if(q[i]==j) cout<<"1 ";
else cout<<"0 ";
cout<<'\n';
}
r++; //解的组数
cout<<"---------------"<<endl;
}
/*
此函数试图在n*n的棋盘的第i行上放一個皇后,
若找到可以放的位置,就递归调用自身试图在i+1行
放另一個皇后,若第i行是最后一行，則打印棋盘。
*/
void Queen::resolve(int i)
{
int j;
// 在第i行给定后检查棋盘上的每一列
for(j=0;j<n;j++) {
//如果在第i行的第j列可以布放皇后
if(!col[j]&&!md[n+i-j-1]&&!sd[i+j]){
Q++;q[i]=j; //布放皇后，第i行皇后在第几列
// 标记新布皇后的攻击范围
col[j]=md[n+i-j-1]=sd[i+j]=1;
// 如果已经布了n个皇后（得到了一组解）,
// 把棋盘（解）打印出來。
if(Q==n) showBoard();
// 否則，递归。在第i行第j列布放皇后的前提下，
//试探下一行(i+1行)在哪一列布皇后？
else if(i<n-1) resolve(i+1);
else resolve(0); //因为约定起始行可以任选
//移除在第i行的第j列新布的皇后，
//并消除所标记的攻击范围，为回溯作准备。
Q--,q[i]=0;
col[j]=md[n+i-j-1]=sd[i+j]=0;
//试探在第i行的第j+1列新布皇后的方案（新解）
}
} //下一列，j循环
//对于给定的行,列扫描完毕后，从这里回溯。
}
void Queen::HowMany()
{
cout<<n<<"皇后問題共有解"<<r<<"组。"<<endl;
}
void main()
{
//定义一个8皇后问题（有92组解）
Queen Q1(8); //大于8，你的微机可能要死机！
//第一个皇后可以在任意一行布放
Q1.resolve(0); //参数在0到n-1之间任选
Q1.HowMany();
}Top
