-
-
Notifications
You must be signed in to change notification settings - Fork 47
/
Copy pathknight_tour.cpp
73 lines (61 loc) · 2.16 KB
/
knight_tour.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
// knight tour dlah urutn gerakan ksatria papan catur
// sehingg ksatria mengunjungi setiap kotak hanya sekali.
// jika ksatria berakhir pada kota yang merupakan langkah
// satu ksatria dari awal persegi (gara bisa langsung
// tur papan lgi, berikut jalur yang sama, tur ditutup;
// jika tidak maka akan terbuka)
#include <array>
#include <iostream>
namespace backtracking {
namespace knight_tour {
template <size_t V>
bool issafe(int x, int y, const std::array<std::array<int, V>, V> &sol) {
return (x < V && x >= 0 && y < V && y >= 0 && sol[x][y] == -1);
}
template <size_t V>
bool solve(int x, int y, int mov, std::array<std::array<int, V>, V> &sol, const std::array<int, V> &xmov, std::array<int, V> &ymov) {
int k = 0, xnext = 0, ynext = 0;
if (mov == V * V) {
return true;
}
for (k = 0; k < V; k++) {
xnext = x + xmov[k];
ynext = y + ymov[k];
if (issafe<V>(xnext, ynext, sol)) {
sol[xnext][ynext] = mov;
if (solve<V>(xnext, ynext, mov + 1, sol, xmov, ymov) == true) {
return true;
} else {
sol[xnext][ynext] = -1;
}
}
}
return false;
}
} // namespace knight_tour
} // namespace backtracking
int main() {
const int n = 8;
std::array<std::array<int, n>, n> sol = {0};
int i = 0, j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
sol[i][j] = -1;
}
}
std::array<int, n> xmov = {2, 1, -1, -2, -2, -1, 1, 2};
std::array<int, n> ymov = {1, 2, 2, 1, -1, -2, -2, -1};
sol[0][0] = 0;
bool flag = backtracking::knight_tour::solve<n>(0, 0, 1, sol, xmov, ymov);
if (flag == false) {
std::cout << "Error: solusi tidak ditemukan\n";
} else {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
std::cout << sol[i][j] << " ";
}
std::cout << "\n";
}
}
return 0;
}