-
Notifications
You must be signed in to change notification settings - Fork 1
/
csp.cpp
106 lines (94 loc) · 3.5 KB
/
csp.cpp
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
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <chrono>
#include "csp.h"
std::vector<int> CSP::solve(bt_heuristic_var var_heuristic, bt_heuristic_val val_heuristic, bool enable_AC, look_ahead lookahead) {
auto start = chrono::high_resolution_clock::now();
if (enable_AC) {
if(not arbre->arc_consistence(-1)) {
return {};
}
}
if(arbre->backtrack(var_heuristic, val_heuristic, lookahead)) {
auto stop = chrono::high_resolution_clock::now();
cout << "Solve time : " << chrono::duration_cast<chrono::milliseconds>(stop - start).count() << " ms" << endl;
return arbre->get_solution();
}
auto stop = chrono::high_resolution_clock::now();
cout << "No solution, time : " << chrono::duration_cast<chrono::milliseconds>(stop - start).count() << " ms" << endl;
return {};
}
void CSP::display_solution() const {
vector<int> solution = arbre->get_solution();
if (solution.empty()) {
cerr << "Solution empty !" << endl;
}
cout << "Solution : " << endl;
for (auto val : solution) {
cout << val << endl;
}
}
void CSP::display_tree_size() const {
arbre->display_tree_size();
}
Reine::Reine(int n){
nb_var = n;
for (int i = 0; i<n; i++){
contraintes_par_var.push_back({});
}
for (int i = 0; i<n; i++){
vector<int> domaine_i;
for (int j = 0; j<n ;j++){
domaine_i.push_back(j);
}
domaines.push_back(domaine_i);
}
for (int i = 0; i<n; i++){
for (int j = i+1; j<n ;j++){
// on crée la contraintes qui lie la reine i à la reine j
Contrainte c = Contrainte(i,domaines[i],j,domaines[j]);
// les reines ne doivent pas être sur la même ligne
c.supprime_relations(1,domaines[i],"-",1,domaines[j],"!=",0);
// les reines ne doivent pas être sur la même diagonale (montante)
c.supprime_relations(1,domaines[i],"-",1,domaines[j],"!=",i-j);
// les reines ne doivent pas être sur la même diagonale (descendante)
c.supprime_relations(1,domaines[i],"-",1,domaines[j],"!=",j-i);
contraintes.push_back(c);
// on indique que les variables i et j sont contraintes par la contraintes que l'on vient de créer
contraintes_par_var[i].push_back(contraintes.size() - 1);
contraintes_par_var[j].push_back(contraintes.size() - 1);
// on indique qu'il y a une contrainte commune à i et j
contraintes_communes.insert(pair<pair<int,int>,int>({i,j},contraintes.size() - 1));
}
}
for (auto &dom : domaines) {
dom.shrink_to_fit();
}
domaines.shrink_to_fit();
contraintes.shrink_to_fit();
for (auto &contr :contraintes_par_var) {
contr.shrink_to_fit();
}
contraintes_par_var.shrink_to_fit();
arbre = new Arbre_dom(domaines, contraintes, contraintes_par_var, contraintes_communes);
}
void Reine::display_solution() const {
vector<int> solution = arbre->get_solution();
if (solution.empty()) {
throw runtime_error("Cannot display empty solution !");
}
cout << " " << string(nb_var * 4 - 1, '-') << "\n";
for (auto i = 0; i < nb_var; i++) {
cout << "|";
for (auto j = 0; j < nb_var; j++) {
if (solution[j] == i) {
cout << " X |";
}
else {
cout << " |";
}
}
cout << "\n"
<< " " << string(nb_var * 4 - 1, '-') << "\n";
}
cout << endl;
}