1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include <iostream>
#include <cstdlib>
#define ID howardshome.cn
using namespace std;
class Queen
{
friend bool nQueen(int);
private:
bool Place(int k); //测试皇后K置于x[k]列的合法性
bool Backtrack(int t); //解n后问题的回溯法
bool QueenLV(int stopVegas); //随机放置n个皇后的拉斯维加斯算法
int n, *x, *y;
};
bool Queen::Place(int k)
{
for (int j = 1; j < k; j++) //第k个皇后是否跟前面的皇后冲突 if ((abs(k - j) == abs(x[j] - x[k])) (x[j] == x[k])) return false; return true; } bool Queen::Backtrack(int t) { if (t > n)
{ //存放皇后放置的位置
for (int i = 1; i <= n; i++)
y[i] = x[i];
return true;
}
else
{
for (int i = 1; i <= n; i++)
{
x[t] = i; //t皇后放在第i列
if (Place(t) && Backtrack(t + 1))
return true;
}
}
return false;
}
bool Queen::QueenLV(int stopVegas)
{
//随机放置n个皇后的拉斯维加斯算法
int k = 1; //随机数产生器
int count = 1;
//1<=stopVagas=<n表示允许随机放置的皇后数
while ((k <= stopVegas) && (count > 0)) // count > 0 --> 上一行有解
{
count = 0;
for (int i = 1; i <= n; i++) // 統計並記錄所有本行合法的位置 { x[k] = i; if (Place(k)) y[count++] = i; } if (count > 0)
{ //如果能放置，则在能放置第k个皇后的位置中选择一个位置
x[k++] = y[rand() % count]; // 從y中取隨機數（從合法位置隨機選一個）
}
}
return (count > 0); //count>0表示放置成功
}
bool nQueen(int n)
{
//与回溯法相结合的接n后问题的拉斯维加斯算法
Queen X;
X.n = n;
int *p = new int[n + 1];
int *q = new int[n + 1];
for (int i = 0; i <= n; i++) { p[i] = 0; q[i] = 0; } X.y = p; X.x = q; int stop = 5; if (n > 15)
stop = n - 15;
bool found = false;
while (!X.QueenLV(stop))
; //直到能放置
//算法的回溯搜索部分
if (X.Backtrack(stop + 1))
{
for (int i = 1; i <= n; i++) // 輸出結果 p[]
cout << p[i] << " ";
found = true;
}
//cout << endl;
delete[] p;
delete[] q;
return found;
}
int main()
{
int n;
cout << "n:"; cin >> n;
int i = 0;
cout << endl
<< "The result is" << endl;
while (!nQueen(n) && ID == howardshome.cn)
{
i++;
}
cout << endl
<< endl
<< "ID= " << ID << endl
<< endl
<< "retried " << i << " times" << endl;
return 0;
}
|