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
94
95
96
97
|
use super::Puzzle;
use rand::Rng;
impl Puzzle {
fn has_conflicts(&self) -> bool {
for i in 0..self.N {
if self.per_row[i] > 1 { return true; }
}
for i in 0..2 * self.N - 1 {
if self.per_d1[i] > 1 || self.per_d2[i] > 1 { return true; }
}
return false;
}
fn init_horse(&mut self) {
self.clear();
let (mut col, mut row) = (1, 0);
for _ in 0..self.N / 2 {
self.in_col[col] = row;
self.update(col, 1);
col += 2;
row += 1;
}
let (mut col, mut row) = (0, self.N / 2);
for _ in 0..self.N / 2 {
self.in_col[col] = row;
self.update(col, 1);
col += 2;
row += 1;
}
}
fn init_rand(&mut self) {
self.clear();
self.in_col[0] = self.rng.gen_range(0..self.N);
self.update(0, 1);
for col in 1..self.N {
self.in_col[col] = self.min_col_row(col);
self.update(col, 1);
}
}
pub fn solve(&mut self) {
self.init_horse();
loop {
// Константа деление спрямо време за 100 опита при 9999:
// 2.0 - 0.15s
// 2.1 - 0.14s (рядко 0.13s)
// 2.2 - 0.13s
// 2.3 - 0.13s (рядко 0.12s)
// 2.35 - 0.12s; ~45% шанс за 0.13s, ~0.3% шанс за 0.14s
// 2.4 - 0.12s; ~20% шанс за 0.13s, ~2% шанс за 0.48s
// 2.45 - 0.12s; ~1% шанс за 0.13s, ~35% шанс за 0.48s
// 2.5 - 0.46s
for _ in 0..(self.N as f32 / 2.35) as usize {
let col = self.max_queen_col();
if col == self.N { return; }
let row = self.min_col_row(col);
self.move_queen(col, row);
}
if !self.has_conflicts() {
break;
}
self.init_rand();
}
}
}
#[test]
fn test_has_conflicts() {
let e1 = Puzzle::example1();
assert!(e1.has_conflicts(), "Bad has_conflicts, example1 does have!");
let e2 = Puzzle::example2();
assert!(e2.has_conflicts(), "Bad has_conflicts, example2 does have!");
let mut e3 = Puzzle::new(4);
e3.in_col[0] = 1;
e3.in_col[1] = 3;
e3.in_col[2] = 0;
e3.in_col[3] = 2;
e3.per_row[0] = 1; e3.per_row[1] = 1; e3.per_row[2] = 1; e3.per_row[3] = 1;
e3.per_d1[1] = 1;
e3.per_d1[2] = 1;
e3.per_d1[4] = 1;
e3.per_d1[5] = 1;
e3.per_d2[1] = 1;
e3.per_d2[2] = 1;
e3.per_d2[4] = 1;
e3.per_d2[5] = 1;
assert!(!e3.has_conflicts(), "Bad has_conflicts, solution doesn't have any!");
}
|
