首页 > 代码库 > 八皇后问题

八皇后问题

2024-07-03 19:33:04   233人阅读

8个皇后的任意两个不能处在同一行，那么肯定是每一个皇后占一行。

于是我们可以定义一个string字符串，字符串中第i个数字表示位于第i行的皇后的列号。

先把string字符串分别用0~7初始化，接下来就是对字符串做全排列。

因为我们用不同的数字初始化字符串，所以任意两个皇后肯定不同列。
我们只需判断每一个排列对应的8个皇后是不是在同一对角线上，

也就是对于string的两个下标i和j，是不是有：

( j - i ) == ( str[i] - str[j] ) 或者 ( i - j ) == ( str[i] - str[j] )。

具体代码如下：

 

 1 void Permutation(string Str, int begin, int end ,vector<string>& vec)//得到全排列
 2 {
 3     if(begin == end - 1) //只剩一个元素
 4     {
 5         vec.push_back(Str);
 6     }
 7     else
 8     {
 9         for(int k = begin; k < end; k++)
10         {
11             swap(Str[k], Str[begin]); //交换两个字符
12             Permutation(Str, begin + 1, end ,vec);
13             swap(Str[k],Str[begin]);  //恢复
14         }
15     } 
16 }
17 
18 void HuangHou(vector<string>& vec)//获得可行方案
19 {
20     string Str = "01234567";
21     Permutation(Str ,0 ,8 ,vec);    
22     for (vector<string>::iterator it = vec.begin() ; it != vec.end() ;)
23     {
24         bool dele = false;
25         string str = *it ;
26         int len = str.length();
27         for (int i = 0 ; i < len ;i++)
28         {
29             for (int j = i+1 ; j < len ;j++)
30             {
31                 if ( ( j - i ) == ( str[i] - str[j] ) || ( i - j ) == ( str[i] - str[j] )  )
32                 {
33                     it = vec.erase(it);
34                     dele = true ;
35                     break;
36                 }
37                 
38             }
39             if (dele == true)
40             {
41                 break;
42             }
43         }
44 
45         if (dele != true)
46         {
47             it++;
48         }
49     }
50 
51 
52 }
53 int main()
54 {
55     vector<string> vec ;
56     HuangHou(vec);
57     cout<<vec.size()<<endl;
58     for (vector<string>::iterator it = vec.begin() ; it != vec.end() ;it++)
59     {
60         cout<<*it<<endl;
61     }
62 
63     getchar();
64     return 0;
65 }

 

每行字符串分别代表0到7行皇后的列位置。

 


联系
我们