a_star_search.cpp

 
#include <algorithm>   
#include <array>       
#include <cassert>     
#include <functional>  
#include <iostream>    
#include <map>         
#include <memory>      
#include <set>         
#include <vector>      
namespace machine_learning {
namespace aystar_search {
template <size_t N = 3>
class EightPuzzle {
    std::array<std::array<uint32_t, N>, N>
        board;  
 
    std::vector<std::pair<int8_t, int8_t>> moves = {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1,
         0}};  
    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};
    }
    inline bool in_range(const uint32_t value) const { return value < N; }
 
 public:
    uint32_t get(size_t i, size_t j) const {
        if (in_range(i) && in_range(j)) {
            return board[i][j];
        }
        return -1;
    }
    std::array<std::array<uint32_t, N>, N> get_state() { return board; }
 
    inline size_t get_size() const { return N; }
    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));
            }
        }
    }
    explicit EightPuzzle(const std::array<std::array<uint32_t, N>, N> &init)
        : board(init) {}
 
    EightPuzzle(const EightPuzzle<N> &A) : board(A.board) {}
 
    EightPuzzle(const EightPuzzle<N> &&A) noexcept
        : board(std::move(A.board)) {}
    ~EightPuzzle() = default;
 
    EightPuzzle &operator=(const EightPuzzle &A) {
        board = A.board;
        return *this;
    }
 
    EightPuzzle &operator=(EightPuzzle &&A) noexcept {
        board = std::move(A.board);
        return *this;
    }
 
    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;
    }
    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;
    }
    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;
    }
    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;
    }
 
    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;
    }
};
template <typename Puzzle>
class AyStarSearch {
    typedef struct Info {
        std::shared_ptr<Puzzle> state;  
        size_t heuristic_value = 0;     
        size_t depth = 0;               
 
        Info() = default;
 
        explicit Info(const Puzzle &A) : state(std::make_shared<Puzzle>(A)) {}
 
        Info(const Puzzle &A, size_t h_value, size_t d)
            : state(std::make_shared<Puzzle>(A)),
              heuristic_value(h_value),
              depth(d) {}
 
        Info(const Info &A)
            : state(std::make_shared<Puzzle>(A.state)),
              heuristic_value(A.heuristic_value),
              depth(A.depth) {}
 
        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)) {}
 
        Info &operator=(const Info &A) {
            state = A.state;
            heuristic_value = A.heuristic_value;
            depth = A.depth;
            return *this;
        }
 
        Info &operator=(Info &&A) noexcept {
            state = std::move(A.state);
            heuristic_value = std::move(A.heuristic_value);
            depth = std::move(A.depth);
            return *this;
        }
        ~Info() = default;
    } Info;
 
    std::shared_ptr<Info> Initial;  // Initial state of the AyStarSearch
    std::shared_ptr<Info> Final;    // Final state of the AyStarSearch
    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>;
    AyStarSearch(const Puzzle &initial, const Puzzle &final) {
        Initial = std::make_shared<Info>(initial);
        Final = std::make_shared<Info>(final);
    }
    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;
    }
    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;                       
        MapOfPuzzleInfoWithInteger g_score;  
        SetOfPuzzleInfo open_list;           
        SetOfPuzzleInfo closed_list;  
 
        // 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
 
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);  
 
    std::vector<matrix3> 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);
    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;
    }
}
int main() {
    test();  // run self-test implementations
    return 0;
}