PROJECT#1.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cstdlib> // For abs
#include <chrono> // For time
using namespace std;


// -------- TYPE & GLOBALS --------
using State = vector<int>;
// Puzzle dimension (Default 3 for 8-puzzles)
int N = 3; 
// Built from N
State goal;
// goalPos[tile] = (row, col)
vector<pair<int,int>> goalPos; 



// -------- GOAL CONSTRUCTION & GOAL TEST --------
// User now can add their size and number placements
void buildGoal(int n) {
    N = n;
    goal.assign(N * N, 0);
    goalPos.assign(N * N, {0, 0});

    for (int i = 0; i < N * N - 1; i++) {
        goal[i] = i + 1;
        goalPos[i + 1] = {i / N, i % N};
    }
    goal[N * N - 1] = 0;
    goalPos[0] = {N - 1, N -1};
}
bool isGoal(const State& s) {
    return s == goal;
}



// ----------- I/O HELPERS -----------
// (Old) Hard coded method for 3x3
// void printBoard(const State& s) {
//     cout << "[" << s[0] << ", " << s[1] << ", " << s[2] << "]\n";
//     cout << "[" << s[3] << ", " << s[4] << ", " << s[5] << "]\n";
//     cout << "[" << s[6] << ", " << s[7] << ", " << s[8] << "]\n";
// }
// User input board
void printBoard(const State& s) {
    for (int r = 0; r < N; r++) {
        cout << "[";
        for (int c = 0; c < N; c++) {
            cout << s[r * N + c];
            if (c != N - 1) cout << ", ";
        }
        cout << "]\n";
    }
}
State readCustomPuzzle() {
    State s(N * N);
    cout << "Enter your puzzle, using a zero to represent the blank.\n";
    cout << "Enter the puzzle delimiting the numbers with a space.\n";

    for (int r = 0; r < N; r++) {
        cout << "Enter row " << (r + 1) << ":\n";
        for (int c = 0; c < N; c++) {
            cin >> s[r * N + c];
        }
    }
    return s;
}



// ---------- VALIDATION HELPERS ----------
string stateKey(const State& s) {
    string key;
    key.reserve(s.size() * 3);
    for (int x : s) {
        key += to_string(x);
        key += ','; // Delimiter to avoid ambiguity (1,11 vs 11,1)
    }
    return key;
}
// Checks legal N X N puzzle inputs
bool isValidPuzzle(const State& s) {
    // Must have N * N tiles 
    if ((int)s.size() != N * N) return false;
    // Checklist array
    vector<int> seen(N * N, 0);
    // Loop over every number typed into the puzzle
    for (int x : s) {
        if (x < 0 || x >= N * N) return false;
        if (seen[x]) return false;
        seen[x] = 1;
    }
    return true;
}
// If puzzle is legal check if it can reach the goal
// Helped from https://www.geeksforgeeks.org/dsa/check-instance-8-puzzle-solvable/ 
// https://www.geeksforgeeks.org/dsa/check-instance-15-puzzle-solvable/ 
bool isSolvable(const State& s) {
    int inversions = 0;

    // Count inversions (ignore 0)
    for (int i = 0; i < N * N; i++) {
        if (s[i] == 0) continue;
        for (int j = i + 1; j < N * N; j++) {
            if (s[j] != 0 && s[i] > s [j]) {
                inversions++;
            }
        }
    }
    
    // If grid width is odd 
    if (N % 2 == 1) {
        return inversions % 2 == 0;
    }

    // If grid width is even
    int blankIndex = 0;
    for (int i = 0; i < N * N; i++) {
        if (s[i] == 0) blankIndex = i;
    }

    // (blankIndex / N) gives blank’s row from top (0-based)
    // (N - that) gives row-from-bottom (1-based)
    int blankRowFromBottom = N - (blankIndex / N);

    // If the sum is odd its solvable 
    // If even unsolvable
    return (blankRowFromBottom + inversions) % 2 == 1;
}



// -------- CORE PUZZLE MECHANICS --------
// A neighbor is generated by swapping the blank (0) with one adjacent tile
vector<State> expand(const State& s) {
    vector<State> neighbors;

    // Find blank location
    int zeroIndex = -1;
    // for (int i = 0; i < 9; i++) {
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == 0) {
            zeroIndex = i;
            break;
        }
    }

    int row = zeroIndex / N;
    int col = zeroIndex % N;

    auto addSwap = [&](int nr, int nc) {
        if (nr < 0 || nr >= N || nc < 0 || nc >= N) return;
        int newIndex = nr * N + nc;
        State newState = s;
        swap(newState[zeroIndex], newState[newIndex]);
        neighbors.push_back(newState);
    };
 
    // Move UP
    addSwap(row - 1, col);
    // Move DOWN
    addSwap(row + 1, col);
    // Move LEFT
    addSwap(row, col - 1);
    // Move RIGHT
    addSwap(row, col + 1);

    return neighbors;
}



// -------- HEURISTICS FOR A* --------
int misplacedTile(const State& s) {
    // # of misplaced tiles from the board
    int count = 0;

    // Loop over all N positions in the board
    for (int i = 0; i < N * N; i++) {
        // Check if the tile is NOT blank (0)
        // AND if its NOT on the same position as in the goal state
        if (s[i] != 0 && s[i] != goal[i]) {
            // Add the amount of misplaced tiles
            count++;
        }
    }
    // Return # of misplaced tiles
    return count;
}
// For each tile (1..N * N - 1), compute how many grid moves it is away from its goal position
// Sum over all tiles. Ignore blank (0)
int manhattanDistance(const State& s) {
    // Total sum of all distances for all tiles
    int total = 0;

    // for (int i = 0; i < 9; i++) {
    for (int i = 0; i < N * N; i++) {
        int tile = s[i];
        if (tile == 0) continue; // Ignore blank

        // Convert index 1D to 2D grid position
        int curRow = i / N;
        int curCol = i % N;
        auto[gr, gc] = goalPos[tile];


        total += abs(curRow - gr) + abs(curCol - gc);
    }
    return total;
}



// ------ CHOOSE ALGO ------
int computeH(const State& s, int algorithm) {
    if (algorithm == 1) return 0;              // UCS
    if (algorithm == 2) return misplacedTile(s); // A* Misplaced
    if (algorithm == 3) return manhattanDistance(s); // A* Manhattan
    return 0; // default UCS
}



// -------- SEARCH STRUCTURES & FUNCTIONS --------
// What we store in the search frontier (UCS and A*)
struct Node {
    State state;
    int g;  // Depth / cost so far (Need for both for UCS and A*) # of moves so far
    int h;  // Heuristic estimate (0 for UCS, # > 0 for A*) # estimate of moves left
    int f;  // priority = g + h (Also for A* misplaced tiles)
};
// Smaller g(n) gets higher priority
struct CompareNode {
    bool operator()(const Node& a, const Node& b) const {
        // Now expand out node with the smallest f = g + h 
        // If theres a tie prefer the one with smaller g 
        if (a.f == b.f) return a.g > b.g; // smallest g first
        return a.f > b.f; // smallest first
    }
};

using Frontier = priority_queue<Node, vector<Node>, CompareNode>;

// --------- GENERAL SEARCH ALGORITHM ---------
// Using General Search Algorithm pseudocode as reference:
bool generalSearch(const State& initial_state, int algorithm, 
    int& solution_depth, int& nodes_expanded, int& max_queue_size) {
    // nodes = MAKE-QUEUE(MAKE-NODE(problem.INITIAL-STATE))
    // Frontier nodes;
    // nodes.push({initial_state, 0});
    Frontier nodes;
    int h0 = computeH(initial_state, algorithm);
    nodes.push({initial_state, 0, h0, 0 + h0});

    unordered_map<string, int> bestNode;
    bestNode[stateKey(initial_state)] = 0;

    nodes_expanded = 0;
    max_queue_size = (int)nodes.size();

    // loop do
    while (true) {
        // if EMPTY(nodes) then return "failure"
        if (nodes.empty()) return false;

        // node = REMOVE-FRONT(nodes)
        Node node = nodes.top();
        nodes.pop();

        string k_node = stateKey(node.state);

        // If this popped node is NOT the best known g for this state, ignore it
        // Prevents expanding outdated duplicates (keeps expansions/queue smaller)
        if (bestNode.count(k_node) && node.g != bestNode[k_node]) {
            continue;
        }

        // Track max queue size (based on frontier size during search)
        if ((int)nodes.size() > max_queue_size) max_queue_size = (int)nodes.size();

        // PRINT TRACE 
        // Shows h(n) = # (any node number)
        cout << "The best state to expand with a g(n) = " << node.g << " and h(n) = " << node.h << " is...\n";

        // Old UCS print made h(n) = 0
        // cout << "The best state to expand with a g(n) = " << node.g << " and h(n) = 0 is... \n";

        printBoard(node.state);
        cout << "\n";

        // if problem.GOAL-TEST(node.STATE) succeeds the return node
        if (isGoal(node.state)) {
            cout << "Goal state!\n\n";
            solution_depth= node.g;
            return true;
        }
        // This is a true "expansion" (So generate children)
        nodes_expanded++;

        // nodes = QUEUEING-FUNCTION(nodes, EXPAND(node, problem.OPERATORS))
        vector<State>nextStates = expand(node.state);

        // Updated now with A* misplaced functionality
        for (const State& s2 : nextStates) {
            int newG = node.g + 1;
            string k = stateKey(s2);

            if (!bestNode.count(k) || newG < bestNode[k]) {
                bestNode[k] = newG;

                int newH = computeH(s2, algorithm);
                int newF = newG + newH;

                nodes.push({s2, newG, newH, newF});
            }
        }

        // Update max after pushing (this is the common definition)
        if ((int)nodes.size() > max_queue_size) max_queue_size = (int)nodes.size();
    }
}



// -------- MAIN --------
int main() {
    // Initial State Handler
    int n;

    while (true) {
        cout << "Enter puzzle dimension N: (3) for 8-puzzle, (4) for 15-puzzle, (5) for 25-puzzle\n";
        
        cin >> n;

        if (n == 3 || n == 4 || n == 5) {
            break;   // valid input
        }

        cout << "\nInvalid dimension. Please enter (3), (4), or (5).\n\n";
    }

    buildGoal(n);

    State start;
    while (true) {
        cout << "Type (1) to use default puzzle, or (2) to create your own.\n";
        int choice;
        cin >> choice;

        if (choice == 1) {
            // Default test 
            if (N == 3) start = {1, 2, 3, 4, 0, 6, 7, 5, 8};
            // Optional safety: ensure default is solvable (prevents infinite search if default changes)
            if (!isSolvable(start)) {
                cout << "\nDefault puzzle is UNSOLVABLE (unexpected). Please try again.\n\n";
                continue;
            }
            else {
                // Simple near-goal default for larger N
                start = goal;
                swap(start[N * N - 1], start[N * N - 2]); // make it one move away-ish
            }
            break; // valid exit loop
        } 
        else if (choice == 2) {
            start = readCustomPuzzle();
            if (!isValidPuzzle(start)) {
                cout << "Invalid puzzle input. Please try again\n";
                continue;
            }
            if (!isSolvable(start)) {
                cout << "\n This puzzle is UNSOLVABLE.\n";
                cout << "Please enter a different puzzle.\n\n";
                continue; 
            }
            break; // valid exit loop
        }
        else {
            cout << "\n Invalid selection. Please enter (1) or (2).\n\n";
        }
    }

    cout << "Select algorithm. (1) for Uniform Cost Search, (2) for Misplaced Tile A*, (3) for Manhattan Distance A*\n";
    int alg;
    cin >> alg;
    if (alg < 1 || alg > 3) {
        cout << "Invalid choice. Please enter from (1), (2), or (3).\n";
        return 0;
    }

    int solution_depth = 0, nodes_expanded = 0, max_queue_size = 0;

    // To record time and add into graphs expermentation
    auto start_time = chrono::high_resolution_clock::now();
    
    bool success = generalSearch(start, alg, solution_depth, nodes_expanded, max_queue_size);

    auto end_time = chrono::high_resolution_clock::now();
    chrono::duration<double> elapsed = end_time - start_time;

    if (!success) {
        // Although I implemented a solveable function this was used before that and to make sure it didnt crash my complier
        cout << "failure\n"; 
    }
    else {
        cout << "Solution depth was " << solution_depth << "\n";
        cout << "Number of nodes expanded: " << nodes_expanded << "\n";
        cout << "Max queue size: " << max_queue_size << "\n";
        cout << "Time taken: " << elapsed.count() << " seconds\n";
    }

    return 0;
}