問題描述:
在一個(gè)N * N的棋盤上放N個(gè)皇后, 并使皇后們不能互相攻擊，
皇后可以橫著、豎著、斜著吃子，
即棋盤上任意兩個(gè)皇后不能同行、同列或在一條對角線上。
以下是我寫的代碼:
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]; // 這里搞不明白，為什么動態(tài)分配的時(shí)候就會出錯(cuò)
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 << "請輸入皇后的個(gè)數(shù): " << 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 << "總數(shù)是：" << count << endl;
83 //------------------------------------------------------------------------
84 system("pause");
85 return(0);
86}
87
88
做是做出來了，但很不完善！
一是：不知道為什么創(chuàng)建對象時(shí)創(chuàng)建的數(shù)組壓棧后不會被修改，而動態(tài)分配創(chuàng)建的數(shù)組壓棧后會被改變
二是：運(yùn)行速度沒老師的那個(gè)版本快
下面附上老師的那個(gè)版本：
1/**//* n皇后問題的深度優(yōu)先算法 */
2
3
4#include <stack>
5#include <iostream>
6#include <string>
7#include <fstream>
8#define M 20 //容許輸入的最大的皇后個(gè)數(shù)
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; //用來存儲擴(kuò)展結(jié)點(diǎn)的堆棧
27 stack < node > resultStack; //保存滿足條件結(jié)點(diǎn)的堆棧
28 node tmpNode,topNode;
29 int i,j,k,l;
30 int queenNum; //皇后個(gè)數(shù)
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); //把第一列擴(kuò)展的狀態(tài)進(jìn)棧
46 }
47 while(!nStack.empty())//當(dāng)堆棧不空時(shí)，對棧頂狀態(tài)結(jié)點(diǎn)進(jìn)行考察
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); //把滿足的結(jié)點(diǎn)進(jìn)堆棧
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
幽幽 閱讀(761)
評論(0) 編輯 收藏 引用 所屬分類:
算法