a_star_search.cpp

/**
 * @brief
 * [A* search algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm)
 * @details
 * A* is an informed search algorithm, or a best-first search, meaning that it
 * is formulated in terms of weighted graphs: starting from a specific starting
 * node of a graph (initial state), it aims to find a path to the given goal
 * node having the smallest cost (least distance travelled, shortest time,
 * etc.). It evaluates by maintaining a tree of paths originating at the start
 * node and extending those paths one edge at a time until it reaches the final
 * state.
 * The weighted edges (or cost) is evaluated on two factors, G score
 * (cost required from starting node or initial state to current state) and H
 * score (cost required from current state to final state). The F(state), then
 * is evaluated as:
 * F(state) = G(state) + H(state).
 *
 * To solve the given search with shortest cost or path possible  is to inspect
 * values having minimum F(state).
 * @author [Ashish Daulatabad](https://github.com/AshishYUO)
 */
#include <algorithm>   /// for `std::reverse` function
#include <array>       /// for `std::array`, representing `EightPuzzle` board
#include <cassert>     /// for `assert`
#include <functional>  /// for `std::function` STL
#include <iostream>    /// for IO operations
#include <map>         /// for `std::map` STL
#include <memory>      /// for `std::shared_ptr`
#include <set>         /// for `std::set` STL
#include <vector>      /// for `std::vector` STL
/**
 * @namespace machine_learning
 * @brief Machine learning algorithms
 */
namespace machine_learning {
/**
 * @namespace aystar_search
 * @brief Functions for [A*
 * Search](https://en.wikipedia.org/wiki/A*_search_algorithm) implementation.
 */
namespace aystar_search {
/**
 * @class EightPuzzle
 * @brief A class defining [EightPuzzle/15-Puzzle
 * game](https://en.wikipedia.org/wiki/15_puzzle).
 * @details
 * A well known 3 x 3 puzzle of the form
 * `
 * 1   2   3
 * 4   5   6
 * 7   8   0
 * `
 * where `0` represents an empty space in the puzzle
 * Given any random state, the goal is to achieve the above configuration
 * (or any other configuration if possible)
 * @tparam N size of the square Puzzle, default is set to 3 (since it is
 * EightPuzzle)
 */
template <size_t N = 3>
class EightPuzzle {
    std::array<std::array<uint32_t, N>, N>
        board;  /// N x N array to store the current state of the Puzzle.

    std::vector<std::pair<int8_t, int8_t>> moves = {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1,
         0}};  /// A helper array to evaluate the next state from current state;
    /**
     * @brief Finds an empty space in puzzle (in this case; a zero)
     * @returns a pair indicating integer distances from top and right
     * respectively, else returns -1, -1
     */
    std::pair<uint32_t, uint32_t> find_zero() {
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                if (!board[i][j]) {
                    return {i, j};
                }
            }
        }
        return {-1, -1};
    }
    /**
     * @brief check whether the index value is bounded within the puzzle area
     * @param value index for the current board
     * @returns `true` if index is within the board, else `false`
     */
    inline bool in_range(const uint32_t value) const { return value < N; }

 public:
    /**
     * @brief get the value from i units from right and j units from left side
     * of the board
     * @param i integer denoting ith row
     * @param j integer denoting column
     * @returns non-negative integer denoting the value at ith row and jth
     * column
     * @returns -1 if invalid i or j position
     */
    uint32_t get(size_t i, size_t j) const {
        if (in_range(i) && in_range(j)) {
            return board[i][j];
        }
        return -1;
    }
    /**
     * @brief Returns the current state of the board
     */
    std::array<std::array<uint32_t, N>, N> get_state() { return board; }

    /**
     * @brief returns the size of the EightPuzzle (number of row / column)
     * @return N, the size of the puzzle.
     */
    inline size_t get_size() const { return N; }
    /**
     * @brief Default constructor for EightPuzzle
     */
    EightPuzzle() {
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                board[i][j] = ((i * 3 + j + 1) % (N * N));
            }
        }
    }
    /**
     * @brief Parameterized Constructor for EightPuzzle
     * @param init a 2-dimensional array denoting a puzzle configuration
     */
    explicit EightPuzzle(const std::array<std::array<uint32_t, N>, N> &init)
        : board(init) {}

    /**
     * @brief Copy constructor
     * @param A a reference of an EightPuzzle
     */
    EightPuzzle(const EightPuzzle<N> &A) : board(A.board) {}

    /**
     * @brief Move constructor
     * @param A a reference of an EightPuzzle
     */
    EightPuzzle(const EightPuzzle<N> &&A) noexcept
        : board(std::move(A.board)) {}
    /**
     * @brief Destructor of EightPuzzle
     */
    ~EightPuzzle() = default;

    /**
     * @brief Copy assignment operator
     * @param A a reference of an EightPuzzle
     */
    EightPuzzle &operator=(const EightPuzzle &A) {
        board = A.board;
        return *this;
    }

    /**
     * @brief Move assignment operator
     * @param A a reference of an EightPuzzle
     */
    EightPuzzle &operator=(EightPuzzle &&A) noexcept {
        board = std::move(A.board);
        return *this;
    }

    /**
     * @brief Find all possible states after processing all possible
     * moves, given the current state of the puzzle
     * @returns list of vector containing all possible next moves
     * @note the implementation is compulsory to create A* search
     */
    std::vector<EightPuzzle<N>> generate_possible_moves() {
        auto zero_pos = find_zero();
        // vector which will contain all possible state from current state
        std::vector<EightPuzzle<N>> NewStates;
        for (auto &move : moves) {
            if (in_range(zero_pos.first + move.first) &&
                in_range(zero_pos.second + move.second)) {
                // swap with the possible moves
                std::array<std::array<uint32_t, N>, N> new_config = board;
                std::swap(new_config[zero_pos.first][zero_pos.second],
                          new_config[zero_pos.first + move.first]
                                    [zero_pos.second + move.second]);
                EightPuzzle<N> new_state(new_config);
                // Store new state and calculate heuristic value, and depth
                NewStates.emplace_back(new_state);
            }
        }
        return NewStates;
    }
    /**
     * @brief check whether two boards are equal
     * @returns `true` if check.state is equal to `this->state`, else
     * `false`
     */
    bool operator==(const EightPuzzle<N> &check) const {
        if (check.get_size() != N) {
            return false;
        }
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                if (board[i][j] != check.board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
    /**
     * @brief check whether one board is lexicographically smaller
     * @returns `true` if this->state is lexicographically smaller than
     * `check.state`, else `false`
     */
    bool operator<(const EightPuzzle<N> &check) const {
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                if (board[i][j] != check.board[i][j]) {
                    return board[i][j] < check.board[i][j];
                }
            }
        }
        return false;
    }
    /**
     * @brief check whether one board is lexicographically smaller or equal
     * @returns `true` if this->state is lexicographically smaller than
     * `check.state` or same, else `false`
     */
    bool operator<=(const EightPuzzle<N> &check) const {
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                if (board[i][j] != check.board[i][j]) {
                    return board[i][j] < check.board[i][j];
                }
            }
        }
        return true;
    }

    /**
     * @brief friend operator to display EightPuzzle<>
     * @param op ostream object
     * @param SomeState a certain state.
     * @returns ostream operator op
     */
    friend std::ostream &operator<<(std::ostream &op,
                                    const EightPuzzle<N> &SomeState) {
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < N; ++j) {
                op << SomeState.board[i][j] << " ";
            }
            op << "\n";
        }
        return op;
    }
};
/**
 * @class AyStarSearch
 * @brief A class defining [A* search
 * algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm). for some
 * initial state and final state
 * @details AyStarSearch class is defined as the informed search algorithm
 * that is formulated in terms of weighted graphs: starting from a specific
 * starting node of a graph (initial state), it aims to find a path to the given
 * goal node having the smallest cost (least distance travelled, shortest time,
 * etc.)
 * The weighted edges (or cost) is evaluated on two factors, G score
 * (cost required from starting node or initial state to current state) and H
 * score (cost required from current state to final state). The `F(state)`, then
 * is evaluated as:
 * `F(state) = G(state) + H(state)`.
 * The best search would be the final state having minimum `F(state)` value
 * @tparam Puzzle denotes the puzzle or problem involving initial state and
 * final state to be solved by A* search.
 * @note 1. The algorithm is referred from pesudocode from
 * [Wikipedia page](https://en.wikipedia.org/wiki/A*_search_algorithm)
 * as is.
 * 2. For `AyStarSearch` to work, the definitions for template Puzzle is
 * compulsory.
 * a. Comparison operator for template Puzzle (`<`, `==`, and `<=`)
 * b. `generate_possible_moves()`
 */
template <typename Puzzle>
class AyStarSearch {
    /**
     * @brief Struct that handles all the information related to the current
     * state.
     */
    typedef struct Info {
        std::shared_ptr<Puzzle> state;  /// Holds the current state.
        size_t heuristic_value = 0;     /// stores h score
        size_t depth = 0;               /// stores g score

        /**
         * @brief Default constructor
         */
        Info() = default;

        /**
         * @brief constructor having Puzzle as parameter
         * @param A a puzzle object
         */
        explicit Info(const Puzzle &A) : state(std::make_shared<Puzzle>(A)) {}

        /**
         * @brief constructor having three parameters
         * @param A a puzzle object
         * @param h_value heuristic value of this puzzle object
         * @param depth the depth at which this node was found during traversal
         */
        Info(const Puzzle &A, size_t h_value, size_t d)
            : state(std::make_shared<Puzzle>(A)),
              heuristic_value(h_value),
              depth(d) {}

        /**
         * @brief Copy constructor
         * @param A Info object reference
         */
        Info(const Info &A)
            : state(std::make_shared<Puzzle>(A.state)),
              heuristic_value(A.heuristic_value),
              depth(A.depth) {}

        /**
         * @brief Move constructor
         * @param A Info object reference
         */
        Info(const Info &&A) noexcept
            : state(std::make_shared<Puzzle>(std::move(A.state))),
              heuristic_value(std::move(A.heuristic_value)),
              depth(std::move(A.depth)) {}

        /**
         * @brief copy assignment operator
         * @param A Info object reference
         */
        Info &operator=(const Info &A) {
            state = A.state;
            heuristic_value = A.heuristic_value;
            depth = A.depth;
            return *this;
        }

        /**
         * @brief move assignment operator
         * @param A Info object reference
         */
        Info &operator=(Info &&A) noexcept {
            state = std::move(A.state);
            heuristic_value = std::move(A.heuristic_value);
            depth = std::move(A.depth);
            return *this;
        }
        /**
         * @brief Destructor for Info
         */
        ~Info() = default;
    } Info;

    std::shared_ptr<Info> Initial;  // Initial state of the AyStarSearch
    std::shared_ptr<Info> Final;    // Final state of the AyStarSearch
    /**
     * @brief Custom comparator for open_list
     */
    struct comparison_operator {
        bool operator()(const std::shared_ptr<Info> &a,
                        const std::shared_ptr<Info> &b) const {
            return *(a->state) < *(b->state);
        }
    };

 public:
    using MapOfPuzzleInfoWithPuzzleInfo =
        std::map<std::shared_ptr<Info>, std::shared_ptr<Info>,
                 comparison_operator>;

    using MapOfPuzzleInfoWithInteger =
        std::map<std::shared_ptr<Info>, uint32_t, comparison_operator>;

    using SetOfPuzzleInfo =
        std::set<std::shared_ptr<Info>, comparison_operator>;
    /**
     * @brief Parameterized constructor for AyStarSearch
     * @param initial denoting initial state of the puzzle
     * @param final denoting final state of the puzzle
     */
    AyStarSearch(const Puzzle &initial, const Puzzle &final) {
        Initial = std::make_shared<Info>(initial);
        Final = std::make_shared<Info>(final);
    }
    /**
     * @brief A helper solution: launches when a solution for AyStarSearch
     * is found
     * @param FinalState the pointer to the obtained final state
     * @param parent_of the list of all parents of nodes stored during A*
     * search
     * @returns the list of moves denoting moves from final state to initial
     * state (in reverse)
     */
    std::vector<Puzzle> Solution(
        std::shared_ptr<Info> FinalState,
        const MapOfPuzzleInfoWithPuzzleInfo &parent_of) {
        //  Useful for traversing from final state to current state.
        auto current_state = FinalState;
        /*
         * For storing the solution tree starting from initial state to
         * final state
         */
        std::vector<Puzzle> answer;
        while (current_state != nullptr) {
            answer.emplace_back(*current_state->state);
            current_state = parent_of.find(current_state)->second;
        }
        return answer;
    }
    /**
     * Main algorithm for finding `FinalState`, given the `InitialState`
     * @param dist the heuristic finction, defined by the user
     * @param permissible_depth the depth at which the A* search discards
     * searching for solution
     * @returns List of moves from Final state to initial state, if
     * evaluated, else returns an empty array
     */
    std::vector<Puzzle> a_star_search(
        const std::function<uint32_t(const Puzzle &, const Puzzle &)> &dist,
        const uint32_t permissible_depth = 30) {
        MapOfPuzzleInfoWithPuzzleInfo
            parent_of;                       /// Stores the parent of the states
        MapOfPuzzleInfoWithInteger g_score;  /// Stores the g_score
        SetOfPuzzleInfo open_list;           /// Stores the list to explore
        SetOfPuzzleInfo closed_list;  /// Stores the list that are explored

        // Before starting the AyStartSearch, initialize the set and maps
        open_list.emplace(Initial);
        parent_of[Initial] = nullptr;
        g_score[Initial] = 0;

        while (!open_list.empty()) {
            // Iterator for state having having lowest f_score.
            typename SetOfPuzzleInfo::iterator it_low_f_score;
            uint32_t min_f_score = 1e9;
            for (auto iter = open_list.begin(); iter != open_list.end();
                 ++iter) {
                // f score here is evaluated by g score (depth) and h score
                // (distance between current state and final state)
                uint32_t f_score = (*iter)->heuristic_value + (*iter)->depth;
                if (f_score < min_f_score) {
                    min_f_score = f_score;
                    it_low_f_score = iter;
                }
            }

            // current_state, stores lowest f score so far for this state.
            std::shared_ptr<Info> current_state = *it_low_f_score;

            // if this current state is equal to final, return
            if (*(current_state->state) == *(Final->state)) {
                return Solution(current_state, parent_of);
            }
            // else remove from open list as visited.
            open_list.erase(it_low_f_score);
            // if current_state has exceeded the allowed depth, skip
            // neighbor checking
            if (current_state->depth >= permissible_depth) {
                continue;
            }
            // Generate all possible moves (neighbors) given the current
            // state
            std::vector<Puzzle> total_possible_moves =
                current_state->state->generate_possible_moves();

            for (Puzzle &neighbor : total_possible_moves) {
                // calculate score of neighbors with respect to
                // current_state
                std::shared_ptr<Info> Neighbor = std::make_shared<Info>(
                    neighbor, dist(neighbor, *(Final->state)),
                    current_state->depth + 1U);
                uint32_t temp_g_score = Neighbor->depth;

                // Check whether this state is explored.
                // If this state is discovered at greater depth, then discard,
                // else remove from closed list and explore the node
                auto closed_list_iter = closed_list.find(Neighbor);
                if (closed_list_iter != closed_list.end()) {
                    // 1. If state in closed list has higher depth, then remove
                    // from list since we have found better option,
                    // 2. Else don't explore this state.
                    if (Neighbor->depth < (*closed_list_iter)->depth) {
                        closed_list.erase(closed_list_iter);
                    } else {
                        continue;
                    }
                }
                auto neighbor_g_score_iter = g_score.find(Neighbor);
                // if the neighbor is already created and has minimum
                // g_score, then update g_score and f_score else insert new
                if (neighbor_g_score_iter != g_score.end()) {
                    if (neighbor_g_score_iter->second > temp_g_score) {
                        neighbor_g_score_iter->second = temp_g_score;
                        parent_of[Neighbor] = current_state;
                    }
                } else {
                    g_score[Neighbor] = temp_g_score;
                    parent_of[Neighbor] = current_state;
                }
                // If this is a new state, insert into open_list
                // else update if the this state has better g score than
                // existing one.
                auto iter = open_list.find(Neighbor);
                if (iter == open_list.end()) {
                    open_list.emplace(Neighbor);
                } else if ((*iter)->depth > Neighbor->depth) {
                    (*iter)->depth = Neighbor->depth;
                }
            }
            closed_list.emplace(current_state);
        }
        // Cannot find the solution, return empty vector
        return std::vector<Puzzle>(0);
    }
};
}  // namespace aystar_search
}  // namespace machine_learning

/**
 * @brief Self test-implementations
 * @returns void
 */
static void test() {
    // Renaming for simplicity
    using matrix3 = std::array<std::array<uint32_t, 3>, 3>;
    using row3 = std::array<uint32_t, 3>;
    using matrix4 = std::array<std::array<uint32_t, 4>, 4>;
    using row4 = std::array<uint32_t, 4>;
    // 1st test: A* search for simple EightPuzzle problem
    matrix3 puzzle;
    puzzle[0] = row3({0, 2, 3});
    puzzle[1] = row3({1, 5, 6});
    puzzle[2] = row3({4, 7, 8});

    matrix3 ideal;
    ideal[0] = row3({1, 2, 3});
    ideal[1] = row3({4, 5, 6});
    ideal[2] = row3({7, 8, 0});

    /*
     * Heuristic function: Manhattan distance
     */
    auto manhattan_distance =
        [](const machine_learning::aystar_search::EightPuzzle<> &first,
           const machine_learning::aystar_search::EightPuzzle<> &second) {
            uint32_t ret = 0;
            for (size_t i = 0; i < first.get_size(); ++i) {
                for (size_t j = 0; j < first.get_size(); ++j) {
                    uint32_t find = first.get(i, j);
                    size_t m = first.get_size(), n = first.get_size();
                    for (size_t k = 0; k < second.get_size(); ++k) {
                        for (size_t l = 0; l < second.get_size(); ++l) {
                            if (find == second.get(k, l)) {
                                std::tie(m, n) = std::make_pair(k, l);
                                break;
                            }
                        }
                        if (m != first.get_size()) {
                            break;
                        }
                    }
                    if (m != first.get_size()) {
                        ret += (std::max(m, i) - std::min(m, i)) +
                               (std::max(n, j) - std::min(n, j));
                    }
                }
            }
            return ret;
        };

    machine_learning::aystar_search::EightPuzzle<> Puzzle(puzzle);
    machine_learning::aystar_search::EightPuzzle<> Ideal(ideal);
    machine_learning::aystar_search::AyStarSearch<
        machine_learning::aystar_search::EightPuzzle<3>>
        search(Puzzle, Ideal);  /// Search object

    std::vector<matrix3> answer;  /// Array that validates the answer

    answer.push_back(
        matrix3({row3({0, 2, 3}), row3({1, 5, 6}), row3({4, 7, 8})}));
    answer.push_back(
        matrix3({row3({1, 2, 3}), row3({0, 5, 6}), row3({4, 7, 8})}));
    answer.push_back(
        matrix3({row3({1, 2, 3}), row3({4, 5, 6}), row3({0, 7, 8})}));
    answer.push_back(
        matrix3({row3({1, 2, 3}), row3({4, 5, 6}), row3({7, 0, 8})}));
    answer.push_back(
        matrix3({row3({1, 2, 3}), row3({4, 5, 6}), row3({7, 8, 0})}));

    auto Solution = search.a_star_search(manhattan_distance);
    std::cout << Solution.size() << std::endl;

    assert(Solution.size() == answer.size());

    uint32_t i = 0;
    for (auto it = Solution.rbegin(); it != Solution.rend(); ++it) {
        assert(it->get_state() == answer[i]);
        ++i;
    }

    // 2nd test: A* search for complicated EightPuzzle problem
    // Initial state
    puzzle[0] = row3({5, 7, 3});
    puzzle[1] = row3({2, 0, 6});
    puzzle[2] = row3({1, 4, 8});
    // Final state
    ideal[0] = row3({1, 2, 3});
    ideal[1] = row3({4, 5, 6});
    ideal[2] = row3({7, 8, 0});

    Puzzle = machine_learning::aystar_search::EightPuzzle<>(puzzle);
    Ideal = machine_learning::aystar_search::EightPuzzle<>(ideal);

    // Initialize the search object
    search = machine_learning::aystar_search::AyStarSearch<
        machine_learning::aystar_search::EightPuzzle<3>>(Puzzle, Ideal);

    Solution = search.a_star_search(manhattan_distance);
    std::cout << Solution.size() << std::endl;
    // Static assertion due to large solution
    assert(13 == Solution.size());
    // Check whether the final state is equal to expected one
    assert(Solution[0].get_state() == ideal);
    for (auto it = Solution.rbegin(); it != Solution.rend(); ++it) {
        std::cout << *it << std::endl;
    }

    // 3rd test: A* search for 15-Puzzle
    // Initial State of the puzzle
    matrix4 puzzle2;
    puzzle2[0] = row4({10, 1, 6, 2});
    puzzle2[1] = row4({5, 8, 4, 3});
    puzzle2[2] = row4({13, 0, 7, 11});
    puzzle2[3] = row4({14, 9, 15, 12});
    // Final state of the puzzle
    matrix4 ideal2;
    ideal2[0] = row4({1, 2, 3, 4});
    ideal2[1] = row4({5, 6, 7, 8});
    ideal2[2] = row4({9, 10, 11, 12});
    ideal2[3] = row4({13, 14, 15, 0});

    // Instantiate states for a*, initial state and final states
    machine_learning::aystar_search::EightPuzzle<4> Puzzle2(puzzle2),
        Ideal2(ideal2);
    // Initialize the search object
    machine_learning::aystar_search::AyStarSearch<
        machine_learning::aystar_search::EightPuzzle<4>>
        search2(Puzzle2, Ideal2);
    /**
     * Heuristic function: Manhattan distance
     */
    auto manhattan_distance2 =
        [](const machine_learning::aystar_search::EightPuzzle<4> &first,
           const machine_learning::aystar_search::EightPuzzle<4> &second) {
            uint32_t ret = 0;
            for (size_t i = 0; i < first.get_size(); ++i) {
                for (size_t j = 0; j < first.get_size(); ++j) {
                    uint32_t find = first.get(i, j);
                    size_t m = first.get_size(), n = first.get_size();
                    for (size_t k = 0; k < second.get_size(); ++k) {
                        for (size_t l = 0; l < second.get_size(); ++l) {
                            if (find == second.get(k, l)) {
                                std::tie(m, n) = std::make_pair(k, l);
                                break;
                            }
                        }
                        if (m != first.get_size()) {
                            break;
                        }
                    }
                    if (m != first.get_size()) {
                        ret += (std::max(m, i) - std::min(m, i)) +
                               (std::max(n, j) - std::min(n, j));
                    }
                }
            }
            return ret;
        };

    auto sol2 = search2.a_star_search(manhattan_distance2);
    std::cout << sol2.size() << std::endl;

    // Static assertion due to large solution
    assert(24 == sol2.size());
    // Check whether the final state is equal to expected one
    assert(sol2[0].get_state() == ideal2);

    for (auto it = sol2.rbegin(); it != sol2.rend(); ++it) {
        std::cout << *it << std::endl;
    }
}
/**
 * @brief Main function
 * @returns 0 on exit
 */
int main() {
    test();  // run self-test implementations
    return 0;
}