EightPuzzleBFS.cpp

#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

struct Node {
    string state;
    shared_ptr<Node> parent;
};

string goal = "123456780";
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void printBoard(const string& state) {
    for (int i = 0; i < 9; ++i) {
        cout << state[i] << ' ';
        if (i % 3 == 2) cout << '\n';
    }
}

void printPath(shared_ptr<Node> node) {
    vector<string> path;
    while (node) {
        path.push_back(node->state);
        node = node->parent;
    }
    reverse(path.begin(), path.end());
    cout << "Solution Path:\n";
    for (const auto& s : path) {
        printBoard(s);
        cout << '\n';
    }
}

bool isValid(int x, int y) {
    return x >= 0 && y >= 0 && x < 3 && y < 3;
}

void bfs(const string& start) {
    queue<shared_ptr<Node>> q;
    unordered_set<string> visited;

    q.push(make_shared<Node>(Node{start, nullptr}));
    visited.insert(start);

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();

        if (curr->state == goal) {
            printPath(curr);
            return;
        }

        int zeroIndex = static_cast<int>(curr->state.find('0'));
        int x = zeroIndex / 3;
        int y = zeroIndex % 3;

        for (auto [dx, dy] : directions) {
            int nx = x + dx;
            int ny = y + dy;

            if (isValid(nx, ny)) {
                int newIndex = nx * 3 + ny;
                string newState = curr->state;
                swap(newState[zeroIndex], newState[newIndex]);

                if (!visited.count(newState)) {
                    visited.insert(newState);
                    q.push(make_shared<Node>(Node{newState, curr}));
                }
            }
        }
    }

    cout << "No solution found.\n";
}

int main() {
    cout << "Enter initial state (use 0 for blank):\n";
    string start;
    cin >> start;
    bfs(start);
    return 0;
}