问题描述:
在一个N * N的棋盘上放N个皇后, 并使皇后们不能互相攻击，
皇后可以横着、竖着、斜着吃子，
即棋盘上任意两个皇后不能同行、同列或在一条对角线上。
以下是我写的代码:
1
#include <iostream>
2#include <stack>
3using namespace std;
4struct point
5
{int x, y;};
6template<class _Ty> class NODE
7{
8
_Ty a[20]; // 这里搞不明白，为什么动态分配的时候就会出错
9// _Ty *a;
10 int count;
11public:
12// NODE(int M=0){a=new _Ty[M];}
13// ~NODE(){delete []a;}
14
_Ty& operator[](int n){return(a[n]);}
15 void setcount(int n){count=n;}
16 int getcount(){return(count);}
17
};
18//----------------------------------------------------------------------------
19int main()
20{
21 int m, count_m, i, j;
22 cout << "请输入皇后的个数: " << endl;
23 cin >> m;
24// m=4; // 测试用
25 stack<NODE<point> > open, close;
26 NODE<point> topnode, tempnode;
27 for( count_m=0; count_m<m; ++count_m) {
28 tempnode[0].x = count_m;
29 tempnode[0].y = 0;
30 tempnode.setcount(0);
31 open.push(tempnode);
32
}
33 while( !open.empty() ) {
34 topnode = open.top();
35 open.pop();
36 if( topnode.getcount() == m-1 )
37 close.push(topnode);
38 else {
39 j = topnode.getcount() + 1;
40 for( count_m=0; count_m<m; ++count_m ) {
41 topnode[j].x = count_m;
42 topnode[j].y = j;
43 for( i=0; i<j; ++i) {
44 if(topnode[j].x > topnode[i].x) {
45 if( (topnode[j].x == topnode[i].x) ||
46 (topnode[j].x - topnode[i].x) == (j-i) )
47 break;
48 }
49 else {
50 if( (topnode[j].x == topnode[i].x) ||
51 (topnode[i].x - topnode[j].x) == (j-i) )
52 break;
53 }
54 }
55 if( i==j ) {
56 topnode.setcount(j);
57 open.push(topnode);
58 }
59 }
60 }
61 }
62 //---------------------------- 输出部分 ----------------------------------
63 int count=0;
64 while( !close.empty() ) {
65 topnode = close.top();
66 close.pop();
67 count++;
68 for( count_m=0; count_m<m; ++count_m ) {
69 printf("(%d,%d) ", topnode[count_m].x, topnode[count_m].y);
70 }
71 cout << endl;
72 for( count_m=0; count_m<m; ++count_m ) {
73 for( i=0; i<m; ++i) {
74 if( i == topnode[count_m].x )
75 cout << "* ";
76 else
77 cout << "- ";
78 }
79 cout << endl;
80 }
81 }
82 cout << "总数是：" << count << endl;
83 //------------------------------------------------------------------------
84 system("pause");
85 return(0);
86}
87
88
做是做出来了，但很不完善！
一是：不知道为什么创建对象时创建的数组压栈后不会被修改，而动态分配创建的数组压栈后会被改变
二是：运行速度没老师的那个版本快
下面附上老师的那个版本：
1/**//* n皇后问题的深度优先算法 */
2
3
4#include <stack>
5#include <iostream>
6#include <string>
7#include <fstream>
8#define M 20 //容许输入的最大的皇后个数
9
10using namespace std;
11
12struct point
13{
14 int x;
15 int y;
16};
17
18struct node
19{
20 point pList[M];
21 int count;
22};
23
24int main()
25{
26 stack < node > nStack; //用来存储扩展结点的堆栈
27 stack < node > resultStack; //保存满足条件结点的堆栈
28 node tmpNode,topNode;
29 int i,j,k,l;
30 int queenNum; //皇后个数
31 bool tmpBool;
32 cout<<"Please input the queen number(<=" << M << "):";
33 cin>>queenNum;
34 while(queenNum>M)
35 {
36 cout<<"The queen number should be < or = " << M <<endl;
37 cout<<"Please input the queen number(<=" << M << "):";
38 cin>>queenNum;
39 }
40 for(i=0;i<queenNum;i++)
41 {
42 tmpNode.pList[0].x=i;
43 tmpNode.pList[0].y=0;
44 tmpNode.count=1;
45 nStack.push(tmpNode); //把第一列扩展的状态进栈
46 }
47 while(!nStack.empty())//当堆栈不空时，对栈顶状态结点进行考察
48 {
49 topNode=nStack.top();
50 nStack.pop();
51 if(topNode.count==queenNum)
52 {
53 //to-do, if satisfy then break;else continue the "while" circulation;
54 resultStack.push(topNode); //把满足的结点进堆栈
55 }
56 else {
57 for(j=0;j<topNode.count;j++)
58 tmpNode.pList[j]=topNode.pList[j];
59 for(i=0;i<queenNum;i++)
60 {
61 tmpBool=false;
62 for(j=0;j<topNode.count;j++)
63 if(i==topNode.pList[j].x||(topNode.pList[j].x-i)== //判断同行同列对角有无皇后
64 (topNode.pList[j].y-topNode.count)||
65 (topNode.pList[j].x-i)==(topNode.count-topNode.pList[j].y))
66 {
67 tmpBool=true;
68 break;
69 }
70 if(tmpBool) continue;
71 tmpNode.pList[topNode.count].x=i;
72 &nb%
posted on 2008-02-10 15:26
幽幽 阅读(759)
评论(0) 编辑 收藏 引用 所属分类:
算法