3
\$\begingroup\$

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 <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);
    }

    return totalPath;

}


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();
}
\$\endgroup\$
2
\$\begingroup\$

I had made a very silly mistake.

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. :)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.