问题描述：实现n皇后问题，要求利用概率算法和回溯法；只需找出一组解即可。
程序设计：
1 #include<iostream>
2 #include<math.h>
3 #include <stdlib.h>
4 #include <ctime>
5 using namespace std;
6 int x[100],q[100];//q[i]=n表示回溯解，x表示概率解
7 int n,cnt = 0;
8 clock_t start1, finish1;
9 clock_t start2, finish2;
10 double totaltime1,totaltime2;
11 //回溯放置皇后时判断是否合法
12 bool find(int a[],int k)
13 {
14 for(int i = 1;i < k;i++)
15 {
16 if(a[i] == a[k] || abs(k-i) == abs(a[k] - a[i]))
17 return false;
18 }
19 return true;
20 }
21 bool Place(int x[],int k)
22 {
23 for (int i = 0;i < k;i++)
24 if(x[i] == x[k] || abs(i - k) == abs(x[i] - x[k]))
25 {
26 return true;
27 }
28 return false;
29 }
30 void print(int n)
31 {
32 int i,j;
33 cnt++;
34
35 cout << "第 " << cnt << " 个解" << endl;
36
37 for(i = 1;i <= n;i++)
38 cout <<"(" << i << "," << q[i] << ")" << " ";//第i行放在第q[i]处。
39 cout << endl;
40
41 for(i = 1;i <= n;i++) //行
42 {
43 for(j = 1;j <= n;j++) //列
44 {
45 if(q[i] != j)
46 printf("x ");
47 else
48 printf("Q ");
49 }
50 cout << endl;
51 }
52 }
53 //回溯法求n皇后
54 void queen(int n){
55 cnt = 0;
56 for(int i = 0;i <= n;i++)//先将所有行的列数清零
57 {
58 q[i] = 0;
59 }
60
61 int k = 1;//k是行数
62 while(k >= 1)
63 {
64 q[k] += 1;
65 while(q[k] <= n )//未到达最后一列
66 {
67 if(find(q,k))
68 break;
69 else
70 q[k]++;//该列不行向后推一个
71 }
72 if(k == n && q[k] <= n)//如果到最后一行，且最后列数正确
73 {
74 for(int i = 1;i <= n;i++)
75 {
76 cout << q[i] << " ";
77
78 }
79 cout << endl;
80 print(n);//将皇后以棋盘式输出
81 }
82 else if(q[k] <= n)//如果还没有到达最后一列，继续下一列
83 {
84 k++;
85 }
86 else//回溯，因为到达最后一行，且列数遍历完，仍没有出结果
87 {
88 q[k] = 0;//让该行的列数重置为0
89 k--;//继续回到上一行
90
91 }
92 }
93 }
94 //类，产生随机数
95 class RandomNumber{//类，这样才能保证不会出现产生的随机值都一样的情况。
96 public:
97 RandomNumber(){
98 srand(time(0));
99 }
100 int get(int begin = 0, int end = 1){//用这个函数可以得到随机值
101 return rand()%(end-begin+1)+begin;
102 }
103 };
104
105
106 bool Queen(int n) //拉斯维加斯概率求解
107 {
108 RandomNumber arr[100];
109
110 int i,j,count=0;// //定义i,j,count. 其中count为试探次数
111 for(i = 0;i < n;)// //其中 n为行数，for循环经过n次，每次代表在第n行中找到皇后所在的列
112 {
113 //为j赋值为一个随机数，此为拉斯维加斯概率算法的核心思想，通过随机性选择快速的引导算法
114 j = arr[i + 1].get(1,n);//这样才可以保证每次的随机数都不一样，如果用j=rand()%n+1;不可以
115
116 x[i]=j; //将随机选取的j作为列向量参与接下来的运算
117 count++;//试探次数加一，用于确定N次运算后n列全部实验完毕
118 if(!Place(x,i)) //这个if语句用于调用冲突子函数以确定是否发生冲突，即这个位置是否可以放置皇后
119 {
120 count=0;
121 i++;
122 }
123 else if(count==n) //位置冲突
124 {
125 return false;
126
127 }
128
129 }
130
131 cout << "拉斯维加斯概率求解" << n << "皇后的一个解为" << endl;
132
133 for(i=0;i<n;i++)// //作为输出结果时的for循环
134 {
135 cout <<"(" << i + 1 << "," << x[i] << ")" << " ";
136
137 }
138 cout << endl;
139 return true;
140 }
141 void runtime()
142 {
143 totaltime1 = finish1 - start1;
144 totaltime2 = finish2 - start2;
145 cout << "回溯法求解"<< n << "皇后的运行时间为" << totaltime1 << "毫秒" << endl;
146 cout << "拉斯维加斯概率算法求解 "<< n << "皇后的运行时间为" << totaltime2 << "毫秒"<< endl;
147 }
148 int choose()
149 {
150 int ch;
151 cout << endl << endl << endl;
152
153 cout << "-----------------------n皇后问题---------------------" << endl;
154 cout << " 请选择你要进行的操作 " << endl;
155 cout << " 1、回溯法求解 2、拉斯维加斯概率算法求解 " << endl;
156 cout << " 3、两种算法运行时间比较 4、退出程序 " << endl;
157 cout << "------------------------------------------------------" << endl;
158 cin >> ch;
159 return ch;
160 }
161 int main()
162 {
163 int ch = choose();
164
165 while(ch != 4)
166 {
167
168 switch (ch) {
169 case 1:
170 printf("请输入皇后的个数(n <= 32),n = :");
171 cin >> n;
172 start1 = clock();//开始计时
173 queen(n);
174 finish1 = clock();
175 break;
176
177 case 2:
178 printf("请输入皇后的个数(n <= 32),n = :");
179 cin >> n;
180 start2 = clock();//开始计时
181 cout << "正在重复测试，请等待······" << endl;
182 while(!Queen(n))
183 {
184 }
185 finish2 = clock();
186 break;
187 case 3:
188 runtime();
189 break;
190 default:
191 exit(0);
192 }
193
194 ch = choose();
195
196 }
197 return 0;
198 }
结果输出：
性能测试：
依次测试n的值在4-11范围内两种算法的程序运行时间，绘制图像如下图所示：
当n=12时，用回溯法求得共有14200个解，时间明显增大：
算法时间复杂度分析：
回溯法：递归n行，每次循环n列，比较0～n - 1次
n * n * (n - 1) / 2，即O(n ^ 3)，O（n * n * (n - 1) / 2) = O(n ^ 3)
拉斯维加斯概率算法：求出一组解的时候，仅需判断每次n行，比较0 ～ n - 1次，即 n * (n - 1) / 2 = O(n ^ 2)
标签：ch,return,clock,int,问题,回溯,皇后,include From： https://www.cnblogs.com/doris510/p/17977296