谁能介绍一下关于 “八皇后”的算法及实现呀？

y-masaki

谁能介绍一下关于 “八皇后”的算法及实现呀？

aero

最简单的就是试探，然后回溯。

guile

1. #include<vector>;
   
2. #include<iostream>;
   
3. using std::vector;
   
4. using std::cout;
   
5. using std::cin;
   
6. using std::endl;
   
7. 
   
8. void print(vector<int>; a,int n)
   
9. {
   
10.         for(int i=0;i<n;i++)
    
11.         {
    
12.                 for(int j=0;j<n;j++)
    
13.                 {
    
14.                         if(a[i]==j)
    
15.                                 cout<<"1 ";
    
16.                         else
    
17.                                 cout<<"0 ";
    
18.                 }
    
19.                 cout<<endl;
    
20.         }
    
21.         cout<<endl;       
    
22. }
    
23. 
    
24. 
    
25. int queen(int n)
    
26. {
    
27.         vector<int>; ivec(n);
    
28.         int i=0,j=0,k=0,num=0;
    
29.         ivec[0]=0;
    
30.         while(i>;=0)
    
31.         {
    
32.                 if(i==0)
    
33.                 {
    
34.                         i++;
    
35.                         ivec[i]=0;
    
36.                         k=0;
    
37.                 }
    
38.                 else if((ivec[i]==ivec[k])||(i-k==ivec[i]-ivec[k])||(k-i==ivec[i]-ivec[k]))
    
39.                 {
    
40.                         ivec[i]++;
    
41.                         k=0;
    
42.                         if(ivec[i]==n)
    
43.                         {
    
44.                                 i--;
    
45.                                 ivec[i]++;
    
46.                                 if(ivec[i]==n)
    
47.                                 {
    
48.                                         i--;
    
49.                                         if(i>;=0)
    
50.                                         {
    
51.                                                 ivec[i]++;
    
52.                                         }
    
53.                                 }
    
54.                         }
    
55.                 }
    
56.                 else
    
57.                 {
    
58.                         k++;
    
59.                         if((i==k)&&(i==n-1))
    
60.                         {
    
61.                                 num++;
    
62.                                 print(ivec,n);
    
63.                                 i--;
    
64.                                 ivec[i]++;
    
65.                                 if(ivec[i]==n)
    
66.                                 {
    
67.                                         i--;
    
68.                                         if(i>;=0)
    
69.                                         {
    
70.                                                 ivec[i]++;
    
71.                                         }
    
72.                                 }
    
73.                                 k=0;
    
74.                         }
    
75.                         else if(i==k)
    
76.                         {
    
77.                                 i++;
    
78.                                 ivec[i]=0;
    
79.                                 k=0;
    
80.                         }
    
81.                 }
    
82.         }       
    
83.         return num;
    
84. }
    
85. 
    
86. int main()
    
87. {
    
88.         int n,num;
    
89.         cin>;>;n;
    
90.         while(n>;0)
    
91.         {
    
92.                 num=queen(n);
    
93.                 cout<<endl<<"There is "<<num<<" answers."<<endl;
    
94.                 cin>;>;n;
    
95.         }
    
96.         return 0;
    
97. }

复制代码