-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.cpp
199 lines (170 loc) · 6.49 KB
/
main.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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
/* A* search algorithm for solving 8 puzzling problem using Hammming and Manhatten cost
Author: Muhammad Faizan
Registration:
Subject: Artifical intelligence
*/
// add some necceassry packages to run this file ..
#include "node.h"
#include "AStar.h"
#include <string.h>
#include <chrono>
void showProgress(aStarSearchAlgorithm &eightPuzzleSolver, const Node &Initial, const Node &Target) {
auto now = Target;
//show the progress for search algorithm.
vector<Node> solPath;
while (eightPuzzleSolver.explored[now].parent_ != EOF) {
solPath.push_back(now);
now = now.getNode(eightPuzzleSolver.explored[now].parent_);
}
solPath.push_back(Initial);
reverse(solPath.begin(), solPath.end());
for (auto &i : solPath) cout << i;
}
void runSearchAlgorithm(const Node &Initial, const Node &Target, int h, bool showProg = true) {
/*run A* search algorithm on initial and goal states given the heuristic
if showProg is true then print the solution.*/
auto *eightPuzzleSearch = new aStarSearchAlgorithm();
eightPuzzleSearch->setHeuristic(h);
auto tic = chrono::steady_clock::now();
int nExpanded = eightPuzzleSearch->AStarSearch(Initial, Target);
auto toc = chrono::steady_clock::now();
auto duration = toc - tic;
cout << "Number of depth Levels (steps): " << (int) eightPuzzleSearch->explored[Target].cost_ << endl;
cout << "Number of Nodes Explored: " << nExpanded << endl;
cout << "Number of Nodes Expanded: " << eightPuzzleSearch->openedTotal << endl;
cout << "Number of Nodes Inserted: " << eightPuzzleSearch->nInserted << endl;
cout << "Maximum possible depth for the soultion: " << eightPuzzleSearch->maximum_depth << endl;
cout << "Duration of the search: " << chrono::duration<double, milli>(duration).count() << "ms" << endl;
cout << endl;
fflush(stdout);
if (showProg) showProgress(*eightPuzzleSearch, Initial, Target);
delete eightPuzzleSearch;
}
int** get_state(unsigned height, unsigned width)
{
int** initial_state = 0;
initial_state = new int*[height];
cout<<"\nInital State Input:\n";
for(int i=0; i<height; i++)
{
initial_state[i] = new int[width];
for(int j=0; j<width; j++)
{
cout<<"\ns["<<i<<"]["<<j<<"]= ";
cin>>initial_state[i][j];
}
}
return initial_state;
}
bool duplicate_check(int state[3][3])
{
int nums[3*3];
// Copy into 1D array
memcpy(nums,state,9*sizeof(int));
// cout<<nums[8]<<endl;
int i, j;
bool duplicate = false;
int size = sizeof(nums)/sizeof(nums[0]);
for(i = 0; i < size; i++)
for(j = i+1; j < size; j++)
if(nums[i] == nums[j]){
duplicate = true; break;}
return duplicate;
}
int main() {
/*the search algoritm will expand the tree to search for the solution. In this case,
I use two types of heuristics, the first one is Hamming heuristic (h1) and the second
one is Manhatten heuristic (h2), both of them are used to measure the estimated cost for
reaching to the goal state
the cost is given by:
f = g + h
where g is the cost from the initial state to the current node where h is the estimated
cost such as hamming or manhatten cost. */
//--------------------------------------------------------------------------------------
// read from the filed, and write our output to the file
// freopen("input_8puzzle.txt", "r", stdin);
// freopen("output_8puzzle.txt", "w", stdout);
// choose grid size, in this case it's 3 (3x3 board)
int gridSize = 3; // for 8 puzzle problem we have 3x3 grid, for other you can specify NXN grid
Node::boardSqSize = gridSize;
// declare Target node as the object of class Node and initialize the goal state, we can
// modify the goal state as per the requirement.
Node Target;
// any gaol state could be assigned.
int goal_state[3][3] = {{1, 2 ,3},
{4, 5, 6},
{7, 8, 0}};
for (int m = 0; m < gridSize; m++)
{
for (int n = 0; n < gridSize; n++)
{
Target.A[m][n] = goal_state[m][n];
}
}
// setting up the initial node and assigning it the initial state of the problem
Node Initial;
// please use the below state for solution check, there are two states given
// one converges and other doesn't. Both of them have been labled.
// any state can be assigned as initial state
// int initial_state[3][3] = {{1, 8 ,2}, // solution exists check ..
// {0, 4, 3},
// {7, 6, 5}};
//get initial state from the user...
int height = 3; // height of grid
int width = 3; // width of the grid
int** initial_state = get_state(height, width);
int start_state[3][3];
// print the inital state
for (int h = 0; h < height; h++)
{
for (int w = 0; w < width; w++)
{
cout<<initial_state[h][w]<<" ";
start_state[h][w] = initial_state[h][w];
Initial.A[h][w] = initial_state[h][w];
}
cout<<"\n";
}
//-----------------------------------------------------------------------
// int initial_state[3][3] = {{8, 1, 3},
// {0, 4, 5}, // when no solutin exists check ...
// {7, 6, 2}};
// for (int i = 0; i < gridSize; i++)
// {
// for (int j = 0; j < gridSize; j++)
// {
// Initial.A[i][j] = initial_state[i][j];
// }
// }
//--------------------------------------------------------------------------
bool duplicate = false;
duplicate = duplicate_check(start_state);
if (!duplicate)
{
cout << "Initial State: \n" << Initial;
cout << "Goal State: \n" << Target;
// pick the heursitic type for h estimation by default I sat it to Manhatten cost
string choose_heuristic = "h2";
// check whether the solution exists or not, if it does then run the search algorithm
// to find the goal state.
if (!Initial.isSolveAble()) {
cout << "Solution doesn't exists!!!!" << endl;
}
// run the algorithm
else
{
if (choose_heuristic == "h1")
{
cout << "Running Hamming heuristic for h estimation: " << endl;
runSearchAlgorithm(Initial, Target, H1, true);}
else{
cout << "Running Manhatten cost for h estimation: "<<endl;
runSearchAlgorithm(Initial, Target, H2, true);
}
}
}
else{
cout<<"Duplicate entries found, please correct the array!!!"<<endl;
}
return 0;
}