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?

Here is a Github link.

```
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

vector solvePuzzle(string state);
vector reconstructPath(map cameFrom, string current);
vector 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 solution = solvePuzzle(state);
cout solvePuzzle(string state) {

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

vector frontier;
vector visited;
map cameFrom;

frontier.push_back(state);

map fScore;
map gScore;
gScore[state] = 0;

while (frontier.size() > 0) {

int best_choice = 0;
float minimum = 100;

for (int index = 0; index minimum) best_choice = index;
}

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

// DEBUGGING

/*
cout path = reconstructPath(cameFrom, curr_state);

cout neighbors = findNeighbors(curr_state);

for (unsigned int index = 0; index = gScore[neighbor]) {
//cout >>>>>>>>>>>>>>>>>>>>>>>>>>
//for (std::map::iterator it=fScore.begin(); it!=fScore.end(); ++it) {
// std::cout first " second ();

}

vector reconstructPath(map cameFrom, string current) {

vector totalPath;
totalPath.push_back(current);

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

current = cameFrom[current];

I had made a very silly mistake.

In this part:

for (int index = 0; 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. :)

StackExchange Code Review Q#160653, answer score: 2