-
Notifications
You must be signed in to change notification settings - Fork 0
/
N_Reinas.cpp
100 lines (77 loc) · 2.26 KB
/
N_Reinas.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
#include <vector>
#include <iostream>
using namespace std;
void n_reinas(vector<int>& sol, int k, vector<bool> filas, vector<bool> d_asc, vector<bool> d_desc);
bool es_solucion(vector<int>& sol, int k, vector<bool> filas, vector<bool> d_asc, vector<bool> d_desc);
bool es_completable(vector<int>& sol, int k, vector<bool> filas, vector<bool> d_asc, vector<bool> d_desc);
bool no_ataca(vector<int>& sol, int k, vector<bool> filas, vector<bool> d_asc, vector<bool> d_desc);
int diag_desc(int x, int y); int diag_asc(int x, int y); void procesar_solucion(vector<int>& sol, int k);
int main()
{
int tam = 4;
vector<int> prueba(tam);
vector<bool> filas(tam);
vector<bool> d_asc(tam);
vector<bool> d_desc(tam);
for (int i = 0; i < tam; i++)
filas[i] = d_asc[i] = d_desc[i] = 0;
n_reinas(prueba, 0, filas, d_asc, d_desc);
system("pause");
return 0;
}
void n_reinas(vector<int>& sol, int k, vector<bool> filas, vector<bool> d_asc, vector<bool> d_desc)
{
for (int c = 0; c < sol.size(); c++)
{
sol[k] = c;
if (es_solucion(sol, k, filas, d_asc, d_desc))
procesar_solucion(sol, k);
else if (es_completable(sol, k, filas, d_asc, d_desc))
{
filas[c] = true;
d_asc[diag_asc(k, c)] = true;
d_desc[diag_desc(k, c)] = true;
n_reinas(sol, k + 1, filas, d_asc, d_desc);
filas[c] = false;
d_asc[diag_asc(k, c)] = false;
d_desc[diag_desc(k, c)] = false;
}
}
}
void procesar_solucion(vector<int>& sol, int k)
{
for (int i = 0; i < sol.size(); i++)
cout << sol[i] << " ";
}
int diag_desc(int x, int y)
{
int num = x - y;
if (num < 0)
num = -num;
return num;
}
int diag_asc(int x, int y)
{
return x + y;
}
bool no_ataca(vector<int>& sol, int k, vector<bool> filas, vector<bool> d_asc, vector<bool> d_desc)
{
bool b = false;
if (!filas[k] && !d_asc[diag_asc(k, sol[k])] && !d_desc[diag_desc(k, sol[k])])
b = true;
return b;
}
bool es_completable(vector<int>& sol, int k, vector<bool> filas, vector<bool> d_asc, vector<bool> d_desc)
{
bool b = false;
if (k < sol.size() && no_ataca(sol, k, filas, d_asc, d_desc))
b = true;
return b;
}
bool es_solucion(vector<int>& sol, int k, vector<bool> filas, vector<bool> d_asc, vector<bool> d_desc)
{
bool b = false;
if (k == sol.size() - 1 && no_ataca(sol, k, filas, d_asc, d_desc))
b = true;
return b;
}