61template <
size_t N = 3>
63 std::array<std::array<uint32_t, N>, N>
66 std::vector<std::pair<int8_t, int8_t>>
moves = {
78 for (
size_t i = 0; i < N; ++i) {
79 for (
size_t j = 0; j < N; ++j) {
92 inline bool in_range(
const uint32_t value)
const {
return value < N; }
104 uint32_t
get(
size_t i,
size_t j)
const {
113 std::array<std::array<uint32_t, N>, N>
get_state() {
return board; }
124 for (
size_t i = 0; i < N; ++i) {
125 for (
size_t j = 0; j < N; ++j) {
126 board[i][j] = ((i * 3 + j + 1) % (N * N));
134 explicit EightPuzzle(
const std::array<std::array<uint32_t, N>, N> &init)
148 : board(std::move(A.board)) {}
168 board = std::move(A.board);
181 std::vector<EightPuzzle<N>> NewStates;
182 for (
auto &move :
moves) {
183 if (
in_range(zero_pos.first + move.first) &&
184 in_range(zero_pos.second + move.second)) {
186 std::array<std::array<uint32_t, N>, N> new_config = board;
187 std::swap(new_config[zero_pos.first][zero_pos.second],
188 new_config[zero_pos.first + move.first]
189 [zero_pos.second + move.second]);
192 NewStates.emplace_back(new_state);
203 if (check.get_size() != N) {
206 for (
size_t i = 0; i < N; ++i) {
207 for (
size_t j = 0; j < N; ++j) {
208 if (board[i][j] != check.board[i][j]) {
221 for (
size_t i = 0; i < N; ++i) {
222 for (
size_t j = 0; j < N; ++j) {
223 if (board[i][j] != check.board[i][j]) {
224 return board[i][j] < check.board[i][j];
236 for (
size_t i = 0; i < N; ++i) {
237 for (
size_t j = 0; j < N; ++j) {
238 if (board[i][j] != check.board[i][j]) {
239 return board[i][j] < check.board[i][j];
254 for (
size_t i = 0; i < N; ++i) {
255 for (
size_t j = 0; j < N; ++j) {
256 op << SomeState.board[i][j] <<
" ";
289template <
typename Puzzle>
296 std::shared_ptr<Puzzle> state;
309 explicit Info(
const Puzzle &A) : state(std::make_shared<Puzzle>(A)) {}
317 Info(
const Puzzle &A,
size_t h_value,
size_t d)
318 : state(std::make_shared<Puzzle>(A)),
327 : state(std::make_shared<Puzzle>(A.state)),
336 : state(std::make_shared<Puzzle>(std::move(A.state))),
338 depth(std::move(A.depth)) {}
356 state = std::move(A.state);
358 depth = std::move(A.depth);
367 std::shared_ptr<Info> Initial;
368 std::shared_ptr<Info> Final;
373 bool operator()(
const std::shared_ptr<Info> &a,
374 const std::shared_ptr<Info> &b)
const {
375 return *(a->state) < *(b->state);
380 using MapOfPuzzleInfoWithPuzzleInfo =
381 std::map<std::shared_ptr<Info>, std::shared_ptr<Info>,
384 using MapOfPuzzleInfoWithInteger =
387 using SetOfPuzzleInfo =
395 Initial = std::make_shared<Info>(initial);
396 Final = std::make_shared<Info>(
final);
408 std::shared_ptr<Info> FinalState,
409 const MapOfPuzzleInfoWithPuzzleInfo &parent_of) {
411 auto current_state = FinalState;
416 std::vector<Puzzle> answer;
417 while (current_state !=
nullptr) {
418 answer.emplace_back(*current_state->state);
419 current_state = parent_of.find(current_state)->second;
432 const std::function<uint32_t(
const Puzzle &,
const Puzzle &)> &dist,
433 const uint32_t permissible_depth = 30) {
434 MapOfPuzzleInfoWithPuzzleInfo
436 MapOfPuzzleInfoWithInteger g_score;
437 SetOfPuzzleInfo open_list;
438 SetOfPuzzleInfo closed_list;
441 open_list.emplace(Initial);
442 parent_of[Initial] =
nullptr;
443 g_score[Initial] = 0;
445 while (!open_list.empty()) {
447 typename SetOfPuzzleInfo::iterator it_low_f_score;
448 uint32_t min_f_score = 1e9;
449 for (
auto iter = open_list.begin(); iter != open_list.end();
453 uint32_t f_score = (*iter)->heuristic_value + (*iter)->depth;
454 if (f_score < min_f_score) {
455 min_f_score = f_score;
456 it_low_f_score = iter;
461 std::shared_ptr<Info> current_state = *it_low_f_score;
464 if (*(current_state->state) == *(Final->state)) {
465 return Solution(current_state, parent_of);
468 open_list.erase(it_low_f_score);
471 if (current_state->depth >= permissible_depth) {
476 std::vector<Puzzle> total_possible_moves =
477 current_state->state->generate_possible_moves();
479 for (Puzzle &neighbor : total_possible_moves) {
482 std::shared_ptr<Info> Neighbor = std::make_shared<Info>(
483 neighbor, dist(neighbor, *(Final->state)),
484 current_state->depth + 1U);
485 uint32_t temp_g_score = Neighbor->depth;
490 auto closed_list_iter = closed_list.find(Neighbor);
491 if (closed_list_iter != closed_list.end()) {
495 if (Neighbor->depth < (*closed_list_iter)->depth) {
496 closed_list.erase(closed_list_iter);
501 auto neighbor_g_score_iter = g_score.find(Neighbor);
504 if (neighbor_g_score_iter != g_score.end()) {
505 if (neighbor_g_score_iter->second > temp_g_score) {
506 neighbor_g_score_iter->second = temp_g_score;
507 parent_of[Neighbor] = current_state;
510 g_score[Neighbor] = temp_g_score;
511 parent_of[Neighbor] = current_state;
516 auto iter = open_list.find(Neighbor);
517 if (iter == open_list.end()) {
518 open_list.emplace(Neighbor);
519 }
else if ((*iter)->depth > Neighbor->depth) {
520 (*iter)->depth = Neighbor->depth;
523 closed_list.emplace(current_state);
526 return std::vector<Puzzle>(0);
538 using matrix3 = std::array<std::array<uint32_t, 3>, 3>;
539 using row3 = std::array<uint32_t, 3>;
540 using matrix4 = std::array<std::array<uint32_t, 4>, 4>;
541 using row4 = std::array<uint32_t, 4>;
544 puzzle[0] = row3({0, 2, 3});
545 puzzle[1] = row3({1, 5, 6});
546 puzzle[2] = row3({4, 7, 8});
549 ideal[0] = row3({1, 2, 3});
550 ideal[1] = row3({4, 5, 6});
551 ideal[2] = row3({7, 8, 0});
556 auto manhattan_distance =
560 for (
size_t i = 0; i < first.
get_size(); ++i) {
561 for (
size_t j = 0; j < first.
get_size(); ++j) {
562 uint32_t
find = first.
get(i, j);
564 for (
size_t k = 0;
k < second.get_size(); ++
k) {
565 for (
size_t l = 0;
l < second.get_size(); ++
l) {
566 if (find == second.get(k, l)) {
567 std::tie(m, n) = std::make_pair(k, l);
576 ret += (std::max(m, i) - std::min(m, i)) +
577 (std::max(n, j) - std::min(n, j));
590 std::vector<matrix3> answer;
593 matrix3({row3({0, 2, 3}), row3({1, 5, 6}), row3({4, 7, 8})}));
595 matrix3({row3({1, 2, 3}), row3({0, 5, 6}), row3({4, 7, 8})}));
597 matrix3({row3({1, 2, 3}), row3({4, 5, 6}), row3({0, 7, 8})}));
599 matrix3({row3({1, 2, 3}), row3({4, 5, 6}), row3({7, 0, 8})}));
601 matrix3({row3({1, 2, 3}), row3({4, 5, 6}), row3({7, 8, 0})}));
604 std::cout <<
Solution.size() << std::endl;
606 assert(
Solution.size() == answer.size());
610 assert(it->get_state() == answer[i]);
616 puzzle[0] = row3({5, 7, 3});
617 puzzle[1] = row3({2, 0, 6});
618 puzzle[2] = row3({1, 4, 8});
620 ideal[0] = row3({1, 2, 3});
621 ideal[1] = row3({4, 5, 6});
622 ideal[2] = row3({7, 8, 0});
632 std::cout <<
Solution.size() << std::endl;
636 assert(
Solution[0].get_state() == ideal);
638 std::cout << *it << std::endl;
644 puzzle2[0] = row4({10, 1, 6, 2});
645 puzzle2[1] = row4({5, 8, 4, 3});
646 puzzle2[2] = row4({13, 0, 7, 11});
647 puzzle2[3] = row4({14, 9, 15, 12});
650 ideal2[0] = row4({1, 2, 3, 4});
651 ideal2[1] = row4({5, 6, 7, 8});
652 ideal2[2] = row4({9, 10, 11, 12});
653 ideal2[3] = row4({13, 14, 15, 0});
661 search2(Puzzle2, Ideal2);
665 auto manhattan_distance2 =
669 for (
size_t i = 0; i < first.
get_size(); ++i) {
670 for (
size_t j = 0; j < first.
get_size(); ++j) {
671 uint32_t
find = first.
get(i, j);
673 for (
size_t k = 0;
k < second.get_size(); ++
k) {
674 for (
size_t l = 0;
l < second.get_size(); ++
l) {
675 if (find == second.get(k, l)) {
676 std::tie(m, n) = std::make_pair(k, l);
685 ret += (std::max(m, i) - std::min(m, i)) +
686 (std::max(n, j) - std::min(n, j));
693 auto sol2 = search2.a_star_search(manhattan_distance2);
694 std::cout << sol2.size() << std::endl;
697 assert(24 == sol2.size());
699 assert(sol2[0].get_state() == ideal2);
701 for (
auto it = sol2.rbegin(); it != sol2.rend(); ++it) {
702 std::cout << *it << std::endl;
A class defining A* search algorithm. for some initial state and final state.
std::vector< Puzzle > Solution(std::shared_ptr< Info > FinalState, const MapOfPuzzleInfoWithPuzzleInfo &parent_of)
A helper solution: launches when a solution for AyStarSearch is found.
struct machine_learning::aystar_search::AyStarSearch::Info Info
Struct that handles all the information related to the current state.
std::vector< Puzzle > a_star_search(const std::function< uint32_t(const Puzzle &, const Puzzle &)> &dist, const uint32_t permissible_depth=30)
AyStarSearch(const Puzzle &initial, const Puzzle &final)
Parameterized constructor for AyStarSearch.
A class defining EightPuzzle/15-Puzzle game.
EightPuzzle & operator=(EightPuzzle &&A) noexcept
Move assignment operator.
~EightPuzzle()=default
Destructor of EightPuzzle.
std::vector< EightPuzzle< N > > generate_possible_moves()
Find all possible states after processing all possible moves, given the current state of the puzzle.
EightPuzzle()
Default constructor for EightPuzzle.
EightPuzzle & operator=(const EightPuzzle &A)
Copy assignment operator.
bool in_range(const uint32_t value) const
check whether the index value is bounded within the puzzle area
bool operator<(const EightPuzzle< N > &check) const
check whether one board is lexicographically smaller
std::pair< uint32_t, uint32_t > find_zero()
A helper array to evaluate the next state from current state;.
friend std::ostream & operator<<(std::ostream &op, const EightPuzzle< N > &SomeState)
friend operator to display EightPuzzle<>
bool operator==(const EightPuzzle< N > &check) const
check whether two boards are equal
uint32_t get(size_t i, size_t j) const
get the value from i units from right and j units from left side of the board
std::vector< std::pair< int8_t, int8_t > > moves
N x N array to store the current state of the Puzzle.
EightPuzzle(const std::array< std::array< uint32_t, N >, N > &init)
Parameterized Constructor for EightPuzzle.
EightPuzzle(const EightPuzzle< N > &A)
Copy constructor.
std::array< std::array< uint32_t, N >, N > get_state()
Returns the current state of the board.
size_t get_size() const
returns the size of the EightPuzzle (number of row / column)
EightPuzzle(const EightPuzzle< N > &&A) noexcept
Move constructor.
bool operator<=(const EightPuzzle< N > &check) const
check whether one board is lexicographically smaller or equal
double k(double x)
Another test function.
double l(double x)
Another test function.
static void test()
Self-test implementations.
Functions for A* Search implementation.
size_t depth
stores h score
size_t heuristic_value
Holds the current state.
Info(const Info &A)
Copy constructor.
Info(const Puzzle &A)
constructor having Puzzle as parameter
Info(const Info &&A) noexcept
Move constructor.
~Info()=default
Destructor for Info.
Info()=default
stores g score
Info & operator=(const Info &A)
copy assignment operator
Info(const Puzzle &A, size_t h_value, size_t d)
constructor having three parameters
Info & operator=(Info &&A) noexcept
move assignment operator
Custom comparator for open_list.