#include #include #include #include #include #include #include enum OPERATION {NO_OP, UP, DOWN, LEFT, RIGHT}; struct Node { std::vector _state; OPERATION _operation; Node* _parent; size_t _level; Node(std::vector& state, OPERATION operation, Node* parent, size_t level) : _state{state}, _operation{operation}, _parent{parent}, _level{level} { } }; struct Equal { std::vector _v; Equal(const std::vector v) : _v{v} { } bool operator() (Node *n) const { return n->_state == _v; } }; std::vector move_tile(std::vector state, OPERATION operation) { // Get the index of the empty tile. short iempty_tile = std::find(state.begin(), state.end(), 0) - state.begin(); short aux; if((operation == LEFT) and (iempty_tile != 0 and iempty_tile != 3 and iempty_tile != 6)) { aux = state[iempty_tile]; state[iempty_tile] = state[iempty_tile - 1]; state[iempty_tile - 1] = aux; return state; } // Move right is not allowed in these indices. else if((operation == RIGHT) and (iempty_tile != 2 and iempty_tile != 5 and iempty_tile != 8)) { aux = state[iempty_tile]; state[iempty_tile] = state[iempty_tile + 1]; state[iempty_tile + 1] = aux; return state; } // Move up is not allowed in these indices. else if((operation == UP) and (iempty_tile != 0 and iempty_tile != 1 and iempty_tile != 2)) { aux = state[iempty_tile]; state[iempty_tile] = state[iempty_tile - 3]; state[iempty_tile - 3] = aux; return state; } // Move down is not allowed in these indices. else if((operation == DOWN) and (iempty_tile != 6 and iempty_tile != 7 and iempty_tile != 8)) { aux = state[iempty_tile]; state[iempty_tile] = state[iempty_tile + 3]; state[iempty_tile + 3] = aux; return state; } else { return {}; } } std::deque expand_node(Node *current_state) { std::deque deque; std::vector v = move_tile(current_state->_state, RIGHT); if(!v.empty()) deque.push_back(new Node(v, RIGHT, current_state, current_state->_level + 1)); v = move_tile(current_state->_state, LEFT); if(!v.empty()) deque.push_back(new Node(v, LEFT, current_state, current_state->_level + 1)); v = move_tile(current_state->_state, UP); if(!v.empty()) deque.push_back(new Node(v, UP, current_state, current_state->_level + 1)); v = move_tile(current_state->_state, DOWN); if(!v.empty()) deque.push_back(new Node(v, DOWN, current_state, current_state->_level + 1)); return deque; } Node* breadth_first_search(std::vector& initial_state, const std::vector& final_state) { Node *root = new Node(initial_state, NO_OP, nullptr, 0); // remember to delete std::deque my_deque; std::set< std::vector > visited; my_deque.push_back(root); while(!my_deque.empty()) { Node* current_state = my_deque.front(); // remember to delete. my_deque.pop_front(); visited.insert(current_state->_state); if(current_state->_state == final_state) { for(auto& e : my_deque) { delete e; e = nullptr; } return current_state; } std::deque possible_paths = expand_node(current_state); //Node* aux; for(auto& path : possible_paths) { // If the state hasn't been visited yet. if(visited.find(path->_state) == visited.end()) { my_deque.insert(my_deque.end(), std::move(path)); visited.insert(path->_state); } else { //aux = path; //path = path->_parent; delete path; path = nullptr; } } } return nullptr; } int main() { std::vector final_state {0,1,2,3,4,5,6,7,8}; std::vector initial_state {8,0,1,2,6,3,4,5,7}; auto start = std::chrono::steady_clock::now(); Node* n = breadth_first_search(initial_state, final_state); Node* aux = nullptr; auto end = std::chrono::steady_clock::now(); auto diff = end - start; std::cout << "\n\n"; if(n == nullptr) { std::cout << "No solution." << '\n'; } else { std::cout << "Initial state \t\t Final State" << '\n'; printf("\n\n%d\t%d\t%d\t | %d\t%d\t%d\n", initial_state[0], initial_state[1], initial_state[2], final_state[0], final_state[1], final_state[2]); printf("\n\n%d\t%d\t%d\t | %d\t%d\t%d\n", initial_state[3], initial_state[4], initial_state[5], final_state[3], final_state[4], final_state[5]); printf("\n\n%d\t%d\t%d\t | %d\t%d\t%d\n", initial_state[6], initial_state[7], initial_state[8], final_state[6], final_state[7], final_state[8]); std::cout << "\nMax search depth: " << n->_level; std::cout << "\nTime: " << std::chrono::duration (diff).count() << " ms" << '\n'; std::cout << "\nMoves (from right to left): "; while(n->_parent != nullptr) { switch(n->_operation) { case NO_OP: break; case UP: std::cout << "UP "; break; case DOWN: std::cout << "DOWN "; break; case LEFT: std::cout << "LEFT "; break; case RIGHT: std::cout << "RIGHT "; break; } // printf("\n\n%d\t%d\t%d\n", n->_state[0], n->_state[1], n->_state[2]); // printf("\n\n%d\t%d\t%d\n", n->_state[3], n->_state[4], n->_state[5]); // printf("\n\n%d\t%d\t%d\n", n->_state[6], n->_state[7], n->_state[8]); aux = n; n = n->_parent; delete aux; aux = nullptr; } } delete n; n = nullptr; return 0; }

8-puzzle, 3x3 problem (memory leaks)