# C++ 8-Sliding Puzzle Solver is very slow

I have made a sliding puzzle solver which is currently for 8-puzzles only. It works too slowly even though it is based on an A* algorithm whose f-score is calculated on the basis of Manhattan Distance and Linear Conflicts. But it solves all the cases correctly.

I would like to improve the time and space consumption of my code. Could you please suggest some improvements?

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <assert.h>

using namespace std;

vector<string> solvePuzzle(string state);
vector<string> reconstructPath(map<string, string> cameFrom, string current);
vector<string> findNeighbors(string state);
float calcfScore(string state);
string to_string(int i);

int main() {

// For Testing Purposes, otherwise we don't need this function

string state;
getline(cin, state);

vector<string> solution = solvePuzzle(state);
cout << "Solution:" << endl;
for (int index = 0; index < solution.size(); index++) cout << solution[index] << endl;

return 0;
}

vector<string> solvePuzzle(string state) {

assert (state.length() == 9);

vector<string> frontier;
vector<string> visited;
map<string, string> cameFrom;

frontier.push_back(state);

map<string, float> fScore;
map<string, int> gScore;
gScore[state] = 0;

while (frontier.size() > 0) {

int best_choice = 0;
float minimum = 100;

for (int index = 0; index < frontier.size(); index++) {
if (fScore[frontier[index]] > minimum) best_choice = index;
}

string curr_state = frontier[best_choice];
frontier.erase(frontier.begin() + best_choice);
visited.push_back(curr_state);

// DEBUGGING

/*
cout << endl << curr_state << endl;// << "Visited: ";
//for (int index = 0; index < visited.size(); index++) cout << visited[index];
cout << endl << "Frontier: ";
for (int index = 0; index < frontier.size(); index++) cout << frontier[index];
cout << endl;
*/

if (curr_state == "123456780") {
vector<string> path = reconstructPath(cameFrom, curr_state);

cout << "No. of fScore's Taken: " << fScore.size() << endl;

return path;
}

vector<string> neighbors = findNeighbors(curr_state);

for (unsigned int index = 0; index < neighbors.size(); index++) {

string neighbor = neighbors[index];
//cout << neighbor;
if (find(visited.begin(), visited.end(), neighbor) != visited.end()) {
//cout << " terminated in visited." << endl;
continue;
}

if (find(frontier.begin(), frontier.end(), neighbor) == frontier.end()) {
//cout << " " << "State not yet Visited. State inserted in Frontier." << endl;
frontier.push_back(neighbor);

} else if ((gScore[curr_state] + 1) >= gScore[neighbor]) {
//cout << " terminated due to idiotic reasons." << endl;
continue;
}

// This path is the best until now. Record it!
cameFrom[neighbor] = curr_state;
gScore[neighbor] = gScore[curr_state] + 1;
fScore[neighbor] = calcfScore(neighbor) + gScore[neighbor];

}

// mapping >>>>>>>>>>>>>>>>>>>>>>>>>>>
//for (std::map<string,float>::iterator it=fScore.begin(); it!=fScore.end(); ++it) {
//    std::cout << it->first << " => " << it->second << '\n';}
//cout << endl;
}

return vector<string>();

}

vector<string> reconstructPath(map<string, string> cameFrom, string current) {

vector<string> totalPath;
totalPath.push_back(current);

while (cameFrom.find(current) != cameFrom.end()) {

current = cameFrom[current];
totalPath.insert(totalPath.begin(), current);
}

}

float calcfScore(string state) {

float fScore = 0;
string finalState = "123456780";

for (int index = 1; index < 9; index++) {
int req_loc = finalState.find(to_string(index));
int loc = state.find(to_string(index));
//cout << index << req_loc << loc << endl;

fScore += abs(req_loc % 3 - loc % 3) + abs(static_cast<int>(req_loc/3) - static_cast<int>(loc/3));

for (int smallIndex = (index - 1 - ((index - 1) % 3)); smallIndex < (index - 1 - ((index - 1) % 3)) + 3; smallIndex++) {

if (smallIndex == index) continue;

if ((smallIndex < index) & (state[smallIndex] > state[index]) & (state[smallIndex] < (index - 1 - ((index - 1) % 3)) + 3)) fScore += 2;
if ((smallIndex > index) & (state[smallIndex] < state[index]) & (state[smallIndex] > (index - 1 - ((index - 1) % 3)))) fScore += 2;

}

}

return fScore;

}

vector<string> findNeighbors(string state) {

vector<string> neighbors;
int index = state.find('0');

if (index % 3 < 2) {
string temp_state = state;
temp_state[index] = state[index + 1];
temp_state[index + 1] = '0';
neighbors.push_back(temp_state);
}

if (index % 3 > 0) {
string temp_state = state;
temp_state[index] = state[index - 1];
temp_state[index - 1] = '0';
neighbors.push_back(temp_state);
}

if (index > 2) {
string temp_state = state;
temp_state[index] = state[index - 3];
temp_state[index - 3] = '0';
neighbors.push_back(temp_state);
}

if (index < 6) {
string temp_state = state;
temp_state[index] = state[index + 3];
temp_state[index + 3] = '0';
neighbors.push_back(temp_state);
}

return neighbors;

}

string to_string(int i)
{
stringstream ss;
ss << i;
return ss.str();
}


In this part:

for (int index = 0; index < frontier.size(); index++) {
if (fScore[frontier[index]] > minimum) best_choice = index;
}


It should have been like this:

for (int index = 0; index < frontier.size(); index++) {
if (fScore[frontier[index]] < minimum) {
best_choice = index;
minimum = fScore[frontier[index]];
}

}


I was doing the opposite. Now it works correctly and fast. Thanks still. :)