8 Puzzle Imran.cpp

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

struct Node {
    int puzzle[5][5];
    int value;
    int state;
};

int goalState[5][5];
int randomPuzzle[5][5];
int temppuzzle[5][5];
int temppuzzle1D[15];
map <string, string> parent;
map <string, int> level;
map <string, int > state;
int stateCnt = 0;
vector <pair <int, int>> getMove;
int dir[2] = {1,-1};
vector <int> visited[5000010];
int visitCnt = 0;
set <string> stVisited;
pair <int, int> goalStateLocation[10];
int eI,eJ;
vector <Node> tempNodepuzzle;

bool compare(Node x1, Node x2) {
    if (x1.value == x2.value)
        return x1.state < x2.state;
    return x1.value < x2.value;
}

bool checkGoalState() {
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            if (goalState[i][j] != temppuzzle[i][j]) {
                return false;
            }
        }
    }
    return true;
}

void temppuzzleTo1D() {
    int cnt = 0;
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++)
            temppuzzle1D[cnt++] = temppuzzle[i][j];
    }
}

void findEmp() {
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            if (temppuzzle[i][j] == 0) {
                eI = i;
                eJ = j;
                return;
            }
        }
    }
}

void genMove() {
    getMove.clear();
    findEmp();
    int empI = eI;
    int empJ = eJ;

    for (int i = 0; i < 2; i++) {
        if (temppuzzle[empI + dir[i]][empJ] != -1)
            getMove.push_back(make_pair(empI + dir[i], empJ));
    }

    for (int i = 0; i < 2; i++) {
        if (temppuzzle[empI][empJ + dir[i]] != -1)
            getMove.push_back(make_pair(empI, empJ + dir[i]));
    }
}

void makeVisit() {
    string s = "";
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            char c = temppuzzle[i][j] + 48;
            s += c;
        }
    }
    stVisited.insert(s);
}

bool chkVisited() {
    string s = "";
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            char c = temppuzzle[i][j] + 48;
            s += c;
        }
    }
    if (stVisited.find(s) == stVisited.end())
        return false;
    else
        return true;
}

void makeTemppuzzle(Node xx) {
    memset(temppuzzle, -1, sizeof(temppuzzle));
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++)
            temppuzzle[i][j] = xx.puzzle[i][j];
    }
}

void initGoalStates() {
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            goalStateLocation[goalState[i][j]] = make_pair(i, j);
        }
    }
}

int calculateManhattanDistance(Node x) {
    int cntTotDist = 0;
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            int xVal = x.puzzle[i][j];
            if (xVal > 0) {
                int igoalState = goalStateLocation[xVal].first;
                int jgoalState = goalStateLocation[xVal].second;
                cntTotDist += abs(i - igoalState);
                cntTotDist += abs(j - jgoalState);
            }
        }
    }

    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            int xgoalState = goalState[i][j];
            int nextgoalState;
            int xVal = x.puzzle[i][j];
            int nextVal;
            if (j + 1 <= 3) {
                nextVal = x.puzzle[i][j + 1];
                nextgoalState = goalState[i][j + 1];

                if (xVal == nextgoalState && xgoalState == nextVal)
                    cntTotDist++;
            }
            if (i + 1 <= 3) {
                nextVal = x.puzzle[i + 1][j];
                nextgoalState = goalState[i + 1][j];
                if (xVal == nextgoalState && xgoalState == nextVal)
                    cntTotDist++;
            }
        }
    }
    return cntTotDist;
}

string NodeToString(Node xx) {
    string s = "";
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            char c = xx.puzzle[i][j] + 48;
            s += c;
        }
    }
    return s;
}

void printPath(string SS) {
    if (parent[SS] == SS) {
        cout << "Step: " << level[SS] << endl;
        for (int i = 0; i < SS.size(); i++) {
            cout << SS[i] << " ";
            if ((i + 1) % 3 == 0)
                cout << endl;
        }
        cout << endl;
        return;
    }

    printPath(parent[SS]);

    cout << "Step: " << level[SS] << endl;
    for (int i = 0; i < SS.size(); i++) {
        cout << SS[i] << " ";
        if ((i + 1) % 3 == 0)
            cout << endl;
    }
    cout << endl;

    return;
}

void Solve() {
    int cnt = 0;
    queue < Node > que;
    Node xx;
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            xx.puzzle[i][j] = randomPuzzle[i][j];
            temppuzzle[i][j] = randomPuzzle[i][j];
        }
    }
    makeVisit();
    que.push(xx);

    string s = NodeToString(xx);
    parent[s] = s;
    level[s] = 0;
    state[s] = stateCnt++;

    bool solved = false;
    while (!que.empty() && !solved) {
        Node u = que.front();
        makeTemppuzzle(u);
        string sU = NodeToString(u);
        genMove();
        int empUI = eI;
        int empUJ = eJ;
        tempNodepuzzle.clear();
        for (int i = 0; i < getMove.size(); i++) {
            int empVI = getMove[i].first;
            int empVJ = getMove[i].second;
            makeTemppuzzle(u);
            swap(temppuzzle[empUI][empUJ], temppuzzle[empVI][empVJ]);

            if (!chkVisited()) {
                Node v;
                for (int ii = 1; ii <= 3; ii++) {
                    for (int jj = 1; jj <= 3; jj++) {
                        v.puzzle[ii][jj] = temppuzzle[ii][jj];
                    }
                }
                string sV = NodeToString(v);
                level[sV] = level[sU] + 1;
                parent[sV] = sU;
                state[sV] = stateCnt;

                v.value = calculateManhattanDistance(v) + level[sV];
                v.state = stateCnt;
                tempNodepuzzle.push_back(v);
                stateCnt++;
            }
        }

        sort(tempNodepuzzle.begin(), tempNodepuzzle.end(), compare);
        for (int i = 0; i < tempNodepuzzle.size(); i++) {
            Node v = tempNodepuzzle[i];
            makeTemppuzzle(v);
            makeVisit();
            que.push(v);

            string sV = NodeToString(v);
            if (checkGoalState()) {
                printPath(sV);
                solved = true;
                cout << "Solved!!" << endl;
                break;
            }
            break;
        }
        que.pop();
    }
    if (!solved)
        cout << "It can not be solved." << endl;
}

int main() {
    randomPuzzle[1][1] = 0;
    randomPuzzle[1][2] = 3;
    randomPuzzle[1][3] = 2;
    randomPuzzle[2][1] = 1;
    randomPuzzle[2][2] = 4;
    randomPuzzle[2][3] = 6;
    randomPuzzle[3][1] = 8;
    randomPuzzle[3][2] = 7;
    randomPuzzle[3][3] = 5;

    goalState[1][1] = 1;
    goalState[1][2] = 2;
    goalState[1][3] = 3;
    goalState[2][1] = 8;
    goalState[2][2] = 0;
    goalState[2][3] = 4;
    goalState[3][1] = 7;
    goalState[3][2] = 6;
    goalState[3][3] = 5;

    initGoalStates();

    cout << "Random puzzle:" << endl << endl;
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++)
            cout << randomPuzzle[i][j] << " ";
        cout << endl;
    }
    cout << endl << endl;

    cout << "Solution: " << endl << endl;
    Solve();

    return 0;
}