EightPuzzleDFS.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;

string goalDFS = "123456780";
set<string> visitedDFS;
vector<string> pathDFS;
vector<pair<int, int>> directionsDFS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

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

bool dfs(const string& state) {
    if (state == goalDFS) {
        pathDFS.push_back(state);
        return true;
    }
    if (visitedDFS.count(state)) return false;

    visitedDFS.insert(state);
    pathDFS.push_back(state);

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

    for (auto [dx, dy] : directionsDFS) {
        int nx = x + dx;
        int ny = y + dy;
        if (isValidDFS(nx, ny)) {
            int newIndex = nx * 3 + ny;
            string newState = state;
            swap(newState[zeroIndex], newState[newIndex]);
            if (dfs(newState)) return true;
        }
    }

    pathDFS.pop_back();
    return false;
}

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

void printPathDFS() {
    cout << "Solution Path:\n";
    for (const auto& s : pathDFS) {
        printBoardDFS(s);
        cout << '\n';
    }
}

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

    if (dfs(start)) printPathDFS();
    else cout << "No solution found.\n";
    return 0;
}