I am trying to write an A* search Algorithm program that solves the classic 8 Puzzle problem. However after many attempts and research I have found myself stuck implementing the algorithm.
The program is required to return the shortest path as a string that represents the actions required to take to reach the goal state from the starting state, for example "UDLRUDLRRDD" U = up, D = down, L = left and R = right.
I am trying to follow the algorithm given by geeksforgeeks(https://www.geeksforgeeks.org/a-search-algorithm/). I Have added a reproducible example below.
Struct to store board states
#include <ctime>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <bits/stdc .h>
enum heuristicFunction{misplacedTiles, manhattanDistance};
struct State{ // state struct to store states of board
int cost = 0, hCost = -1, gCost = 0; // total cost F(n) = H(n) G(n)
int state[3][3]; // Board, the blank tile is represented as 0
int x, y; // 0 pos
string action; // stores the action the state took
State *parent = NULL;
// default state constructor
State(const string element){
int n;
n = 0;
for(int i=0; i < 3; i ){
for(int j=0; j < 3; j ){
state[i][j] = element[n] - '0';
if(state[i][j] == 0){
x = j;
y = i;
}
n ;
}
}
}
// copy constructor
State(State *s){
for(int i=0; i<3; i ){
for(int j=0; j<3; j ){
this->state[i][j] = s->state[i][j];
}
}
this->x = s->x;
this->y = s->y;
this->cost = s->cost;
this->hCost = s->hCost;
this->gCost = s->gCost;
this->action = s->action;
this->parent = s->parent;
}
};
A* search class that implements the struct above
class AStarSearch{
private:
struct Cost_Compare{ // struct containing operator for cost organize Q
bool operator()(State* const& n1, State* const& n2) {
return n1->cost > n2->cost; // return true if n1 cost is greater
}
};
// Containers
priority_queue<State*, vector<State*>, Cost_Compare> Queue; // Q container
vector<State*> visitedList; // visited list
// start and end states
State *initial_state;
State *final_state;
// heuristic enum
heuristicFunction heuristic;
public:
// constructor
AStarSearch(const string init, const string final, heuristicFunction heuristic){
this->initial_state = new State(init); // set init state
this->final_state = new State(final); // set final state
this->Queue.push(this->initial_state); // push init state to queue
this->heuristic = heuristic;
}
State *getInit(){
return this->initial_state;
}
State *getFinal(){
return this->final_state;
}
// Cost Functions
State* Calculate_H(State *n){
int sum = 0;
switch(heuristic){
case misplacedTiles:
for(int i = 0; i < 3; i ){
for(int j = 0; j < 3; j ){
if(n->state[i][j] != final_state->state[i][j]){
sum ;
}
}
}
n->hCost = sum;
break;
case manhattanDistance:
for (int i = 0; i < 3; i ) {
for (int j = 0; j < 3; j ) {
if(n->state[i][j] != 0){
for (int k = 0; k < 3; k ) {
for (int l = 0; l < 3; l ) {
if (n->state[i][j] == final_state->state[k][l]) {
sum = abs(i-k) abs(j-l);
}
}
}
}
}
}
n->hCost = sum;
break;
}
return n;
}
int calculate_cost(State *n){
int cost;
cost = n->hCost n->gCost;
return cost;
}
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
// State Actions
State* move_left(State* current){
State *curr = new State(current);
// Move Blank tile
swap(&curr->state[curr->y][curr->x], &curr->state[curr->y][curr->x-1]);
curr->x = curr->x - 1;
curr = Calculate_H(curr); // calculate hCost
curr->gCost = curr->gCost 1; // add depth
curr->cost = calculate_cost(curr); // calc total tile cost
curr->action = "L";
curr->parent = current; // assign parent node
return curr;
}
State* move_right(State* current){
State *curr = new State(current);
// Move Blank tile
swap(&curr->state[curr->y][curr->x], &curr->state[curr->y][curr->x 1]);
curr->x = curr->x 1;
curr = Calculate_H(curr); // calculate hCost
curr->gCost = curr->gCost 1; // add depth
curr->cost = calculate_cost(curr); // calc total tile cost
curr->action = "R";
curr->parent = current; // assign parent node
return curr;
}
State* move_down(State* current){
State *curr = new State(current);
// Move Blank tile
swap(&curr->state[curr->y][curr->x], &curr->state[curr->y 1][curr->x]);
curr->y = curr->y 1;
curr = Calculate_H(curr); // calculate hCost
curr->gCost = curr->gCost 1; // add depth
curr->cost = calculate_cost(curr); // calc total tile cost
curr->action = "D";
curr->parent = current; // assign parent node
return curr;
}
State* move_up(State* current){
State *curr = new State(current);
// Move Blank tile
swap(&curr->state[curr->y][curr->x], &curr->state[curr->y-1][curr->x]);
curr->y = curr->y - 1;
curr = Calculate_H(curr); // calculate hCost
curr->gCost = curr->gCost 1; // add depth
curr->cost = calculate_cost(curr); // calc total tile cost
curr->action = "U";
curr->parent = current; // assign parent node
return curr;
}
bool isEqual(State *s1, State *s2){
for(int i=0; i<3; i )
for(int j=0; j<3; j )
if(s1->state[i][j] != s2->state[i][j])
return false;
return true;
}
bool isPresentInVisited(State *curr){
bool flag1 = false;
for(int i=0; i<visitedList.size(); i ){
if(isEqual(curr, visitedList[i])){
return true;
}
}
return false;
}
bool isPresentInQueue(State *s1, priority_queue<State*, vector<State*>, Cost_Compare> q){
while(!q.empty()){
State *curr = q.top();
q.pop();
if(isEqual(s1, curr)){
return true;
}
}
return false;
}
void search(){
State *current = Queue.top();
if(current->hCost == 0){
visitedList.push_back(current);
return;
}
while(!Queue.empty()){
State* next_state; // next state
next_state = Queue.top(); // assign to top of Q
Queue.pop(); // pop element off Q
visitedList.push_back(next_state); // add to visited list
vector<State*> successors;
if(next_state->hCost == 0){ // check goal
return;
} // else expand state
// expansions
else if(next_state->x == 0 && next_state->y == 0){
/*
0 1 2 0->down
3 4 5 0->right
6 7 8
*/
State *down = move_down(next_state);
State *right = move_right(next_state);
successors.push_back(down);
successors.push_back(right);
}
else if(next_state->x == 0 && next_state->y == 1){
/*
1 0 2 0->down
3 4 5 0->right
6 7 8 0->left
*/
State *down = move_down(next_state);
State *right = move_right(next_state);
State *left = move_left(next_state);
successors.push_back(down);
successors.push_back(right);
successors.push_back(left);
}
else if(next_state->x == 0 && next_state->y == 2){
/*
1 2 0 0->down
3 4 5 0->left
6 7 8
*/
State *down = move_down(next_state);
State *left = move_left(next_state);
successors.push_back(down);
successors.push_back(left);
}
else if(next_state->x == 1 && next_state->y == 0){
/*
1 2 3 0->down
0 4 5 0->left
6 7 8 0->up
*/
State *down = move_down(next_state);
State *left = move_left(next_state);
State *up = move_up(next_state);
successors.push_back(down);
successors.push_back(left);
successors.push_back(up);
}
else if(next_state->x == 1 && next_state->y == 1){
/*
1 2 3 0->down
4 0 5 0->left
6 7 8 0->up, 0-right
*/
State *down = move_down(next_state);
State *left = move_left(next_state);
State *right = move_right(next_state);
State *up = move_up(next_state);
successors.push_back(down);
successors.push_back(left);
successors.push_back(right);
successors.push_back(up);
}
else if(next_state->x == 1 && next_state->y == 2){
/*
1 2 3 0->down
4 5 0 0->left
6 7 8 0->up
*/
State *down = move_down(next_state);
State *left = move_left(next_state);
State *up = move_up(next_state);
successors.push_back(down);
successors.push_back(left);
successors.push_back(up);
}
else if(next_state->x == 2 && next_state->y == 0){
/*
1 2 3
4 5 6 0->right
0 7 8 0->up
*/
State *right = move_right(next_state);
State *up = move_up(next_state);
successors.push_back(right);
successors.push_back(up);
}
else if(next_state->x == 2 && next_state->y == 1){
/*
1 2 3 0->right
4 5 6 0->left
7 0 8 0->up
*/
State *left = move_left(next_state);
State *right = move_right(next_state);
State *up = move_up(next_state);
successors.push_back(left);
successors.push_back(right);
successors.push_back(up);
}
else if(next_state->x == 2 && next_state->y == 2){
/*
1 2 3 0->up
4 5 6 0->left
7 8 0
*/
State *up = move_up(next_state);
State *left = move_left(next_state);
successors.push_back(up);
successors.push_back(left);
}
for(int i=0; i<successors.size(); i ){
if(successors[i]->hCost==0){
visitedList.push_back(successors[i]);
return;
}
else if(!isPresentInVisited(successors[i]) && !isPresentInQueue(successors[i], Queue)){
Queue.push(successors[i]);
}
}
}
return;
}
priority_queue<State*, vector<State*>, Cost_Compare> getQueue(){
return this->Queue;
}
vector<State*> getVisited(){
return this->visitedList;
}
};
This is where the class is implemented. The initial state and goal state are strings that follow this format: initialState = "042158367" and goalState = "012345678"
string aStar_search(string const initialState, string const goalState, heuristicFunction heuristic){
string path; // final path
// a star start
State *state;
vector<string> pathVector;
AStarSearch search = AStarSearch(initialState, goalState, heuristic);
search.search(); // begin search
state = search.getVisited()[search.getVisited().size()-1]; // assign last state this should the goal state
// debug expected goal state of the board
cout << endl << "Goal State: "<< endl;
for(int i=0; i < 3; i ){
for(int j=0; j < 3; j ){
cout << search.getFinal()->state[i][j];
}
cout << endl;
}
// debug the initial state of the board
cout << endl << "init State: "<< endl;
for(int i=0; i < 3; i ){
for(int j=0; j < 3; j ){
cout << search.getInit()->state[i][j];
}
cout << endl;
}
// debug this should be the same as goal state
cout << endl << "Goal State from visitedList: "<< endl;
for(int i=0; i < 3; i ){
for(int j=0; j < 3; j ){
cout << state->state[i][j];
}
cout << endl;
}
while(state->parent){ // iter back through parents of states
pathVector.push_back(state->action); // push actions to vector
state = state->parent; // next parent
}
for(int i = pathVector.size()-1; i >= 0; i--){ // need to iter backwards because we follow the perant states
path = pathVector[i]; // add to path
}
// aStar exit
cout << endl << "Path To Goal: " << path << endl;
return path;
}
I believe my implementation of the search function is flawed as when I print the goal state from the visited list I get a completely different state than the expected goal state and hence this returns the incorrect path. For example when I set initialState = "042158367" and goalState = "012345678" I get the following output in the console
Goal State:
012
345
678
init State:
042
158
367
Goal State from visitedList:
514
082
367
Path To Goal: DRULDRRUR
I was wondering if someone could take a look at my code and tell me where I am going wrong in the implementation of the algorithm. Any help would be greatly appreciated.
Thanks
CodePudding user response：
The problem was the coordinates in the expanded states if statement, the x and y values were the wrong way around. facepalm
// expansions
else if(next_state->x == 0 && next_state->y == 0){
/*
0 1 2 0->down
3 4 5 0->right
6 7 8
*/
State *down = move_down(next_state);
State *right = move_right(next_state);
successors.push_back(down);
successors.push_back(right);
}
else if(next_state->x == 1 && next_state->y == 0){
/*
1 0 2 0->down
3 4 5 0->right
6 7 8 0->left
*/
State *down = move_down(next_state);
State *right = move_right(next_state);
State *left = move_left(next_state);
successors.push_back(down);
successors.push_back(right);
successors.push_back(left);
}
else if(next_state->x == 2 && next_state->y == 0){
/*
1 2 0 0->down
3 4 5 0->left
6 7 8
*/
State *down = move_down(next_state);
State *left = move_left(next_state);
successors.push_back(down);
successors.push_back(left);
}
else if(next_state->x == 0 && next_state->y == 1){
/*
1 2 3 0->down
0 4 5 0->left
6 7 8 0->up
*/
State *down = move_down(next_state);
State *left = move_left(next_state);
State *up = move_up(next_state);
successors.push_back(down);
successors.push_back(left);
successors.push_back(up);
}
else if(next_state->x == 1 && next_state->y == 1){
/*
1 2 3 0->down
4 0 5 0->left
6 7 8 0->up, 0-right
*/
State *down = move_down(next_state);
State *left = move_left(next_state);
State *right = move_right(next_state);
State *up = move_up(next_state);
successors.push_back(down);
successors.push_back(left);
successors.push_back(right);
successors.push_back(up);
}
else if(next_state->x == 2 && next_state->y == 1){
/*
1 2 3 0->down
4 5 0 0->left
6 7 8 0->up
*/
State *down = move_down(next_state);
State *left = move_left(next_state);
State *up = move_up(next_state);
successors.push_back(down);
successors.push_back(left);
successors.push_back(up);
}
else if(next_state->x == 0 && next_state->y == 2){
/*
1 2 3
4 5 6 0->right
0 7 8 0->up
*/
State *right = move_right(next_state);
State *up = move_up(next_state);
successors.push_back(right);
successors.push_back(up);
}
else if(next_state->x == 1 && next_state->y == 2){
/*
1 2 3 0->right
4 5 6 0->left
7 0 8 0->up
*/
State *left = move_left(next_state);
State *right = move_right(next_state);
State *up = move_up(next_state);
successors.push_back(left);
successors.push_back(right);
successors.push_back(up);
}
else if(next_state->x == 2 && next_state->y == 2){
/*
1 2 3 0->up
4 5 6 0->left
7 8 0
*/
State *up = move_up(next_state);
State *left = move_left(next_state);
successors.push_back(up);
successors.push_back(left);
}
CodePudding user response：
Thanks for very interesting question!
Although you're asking to fix a bug in your code, on contrary I decided to implement my own solution from scratch. So I don't claim for my answer to be accepted, although I hope my solution would be interesting at least for someone from educational point of view.
I implemented step by step details from Wikipedia Article about A* Search Algorithm. Though my solution has its own programming details, mostly due to extensive usage of standard C library.
Before implementing algorithm located in function AStarSolve() I created a helper supplementary class Board which gives different helper methods to access game Board.
You may see that at the top of code I created two constants n = 3, m = 3 - this is to allow any board size, my board has NxM dimensions, currently only 3x3 as in your original task, but it can be set to any non-square size.
As you know A-Star has so called heuristic function estimating lowest possible cost (lower bound) for the path, this function is signified as H(path).
In my code H(x) is taken as sum of distances of every non-zero cell to final position. It is quite obvious to prove that this is a lower bound, and in fact quite good.
In A-Star algorithm this lower bound H(x) only influences speed of convergence of algorithm, so the better its estimate the faster we find the answer. But even with H(x) = 0 we will find the answer, in fact with 0 bound A Star algorithm becomes exactly Dijkstra Algorithm of finding shortest path, hence A Star is generalization of Dijkstra.
I also had idea to make my algorithm multi-core, incorporating all CPU threads, but right now it is only single core just for educational simplicity. If I have desire later I'll extend my answer with multi-core version.
Following code does this console output of solution:
042 142 142 142 142
158 --> 058 --> 358 --> 358 --> 358 -->
367 367 067 607 670
142 142 102 012
350 --> 305 --> 345 --> 345
678 678 678 678
#include <iostream>
#include <stdexcept>
#include <map>
#include <set>
#include <functional>
#include <string>
#include <vector>
#include <unordered_map>
#define ASSERT_MSG(cond, msg) { if (!(cond)) throw std::runtime_error("Assertion (" #cond ") failed at line " std::to_string(__LINE__) "! Msg '" std::string(msg) "'."); }
#define ASSERT(cond) ASSERT_MSG(cond, "")
using u8 = uint8_t;
size_t constexpr n = 3, m = 3;
class Board {
public:
Board() : n_(n), m_(m), board_(n_ * m_) {}
Board(std::string const & s) : n_(n), m_(m), board_(n_ * m_) {
for (size_t i = 0; i < m_; i)
for (size_t j = 0; j < n_; j)
(*this)(i, j) = s.at(i * m_ j) - '0';
}
u8 & operator () (size_t i, size_t j) { return board_[i * m_ j]; }
u8 const & operator () (size_t i, size_t j) const { return const_cast<Board&>(*this)(i, j); }
bool operator == (Board const & o) const { return board_ == o.board_; }
std::vector<Board> Neighbours() const {
std::vector<Board> r;
for (ptrdiff_t i = 0; i < n_; i)
for (ptrdiff_t j = 0; j < m_; j)
if ((*this)(i, j) == 0) {
for (std::pair<int, int> p: std::vector<std::pair<int, int>>{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}) {
ptrdiff_t const ni = i p.first, nj = j p.second;
if (ni < 0 || ni >= n_ || nj < 0 || nj >= m_)
continue;
Board o = *this;
std::swap(o(i, j), o(ni, nj));
r.push_back(std::move(o));
}
break;
}
return std::move(r);
}
std::string Str(bool newline = false) const {
std::string r;
for (size_t i = 0; i < n_; i) {
for (size_t j = 0; j < m_; j)
r.append(1, (*this)(i, j) '0');
if (newline && i 1 < n_)
r.append(1, '\n');
}
return r;
}
size_t MinDist(Board const & to) const {
size_t r = 0;
for (ptrdiff_t i = 0; i < n_; i)
for (ptrdiff_t j = 0; j < m_; j) {
auto const v = (*this)(i, j);
if (v == 0)
continue;
size_t dist = size_t(-1);
for (ptrdiff_t i2 = 0; i2 < n_; i2) {
for (ptrdiff_t j2 = 0; j2 < m_; j2)
if (to(i2, j2) == v) {
dist = std::abs(i - i2) std::abs(j - j2);
break;
}
if (dist != size_t(-1))
break;
}
ASSERT(dist != -1);
r = dist;
}
return r;
}
private:
size_t n_ = 0, m_ = 0;
std::vector<u8> board_;
};
std::vector<Board> AStarSolve(Board const & start, Board const & goal) {
// https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode
using IdT = std::string;
struct Entry {
Board board;
size_t gscore = size_t(-1), fscore = size_t(-1);
IdT came_from{};
};
std::unordered_map<IdT, Entry> entries;
std::map<size_t, std::set<IdT>> open_set;
auto H = [&](Entry const & e) {
return e.board.MinDist(goal);
};
{
Entry first{.board = start, .gscore = 0};
first.fscore = H(first);
entries[first.board.Str()] = first;
open_set[first.fscore].insert(first.board.Str());
}
std::function<std::vector<Board>(IdT const &, size_t)> ReconstructPath =
[&](IdT const & id, size_t depth){
thread_local std::vector<Board> path;
if (id == IdT{})
return path;
if (depth == 0)
path.clear();
auto const & e = entries.at(id);
path.insert(path.begin(), e.board);
return ReconstructPath(e.came_from, depth 1);
};
while (!open_set.empty()) {
auto const min_fscore = open_set.begin()->first;
auto const min_entries = open_set.begin()->second;
for (auto const & id: min_entries)
if (entries.at(id).board == goal)
return ReconstructPath(id, 0);
open_set.erase(min_fscore);
for (auto const & cid: min_entries) {
auto const & cure = entries.at(cid);
for (auto const & nbid: cure.board.Neighbours()) {
size_t const tentative_gscore = cure.gscore 1;
auto const nid = nbid.Str();
auto it = entries.find(nid);
bool is_new = it == entries.end();
if (is_new || tentative_gscore < it->second.gscore) {
if (is_new)
it = entries.insert({nid, Entry{.board = nbid}}).first;
it->second.came_from = cid;
it->second.gscore = tentative_gscore;
if (!is_new) {
auto it2 = open_set.find(it->second.fscore);
if (it2 != open_set.end() && it2->second.count(nid)) {
it2->second.erase(nid);
if (it2->second.empty())
open_set.erase(it2);
}
}
it->second.fscore = tentative_gscore H(it->second);
open_set[it->second.fscore].insert(nid);
}
}
}
}
ASSERT_MSG(false, "Unreachable!");
}
void Solve(std::string const & start, std::string const & goal) {
auto const v = AStarSolve(start, goal);
size_t constexpr per_line = 5;
bool last = false;
for (size_t i = 0; !last; i) {
for (size_t j = 0; j < n; j) {
for (size_t i2 = 0; i2 < per_line; i2) {
size_t const k = i * per_line i2;
if (k >= v.size()) {
last = true;
for (size_t l = 0; l < (m 5); l)
std::cout << " ";
} else {
auto const & e = v.at(k);
auto const s = e.Str(true);
size_t pos = 0;
for (size_t ip = 0; ip < j; ip)
pos = s.find('\n', pos) 1;
size_t pos2 = std::min<size_t>(s.size(), s.find('\n', pos));
std::cout << s.substr(pos, pos2 - pos) << (j == (n / 2) && k 1 < v.size() ? " --> " : " ");
}
std::cout << (i2 1 >= per_line ? "\n" : "");
}
}
std::cout << std::endl;
}
}
int main() {
try {
Solve("042158367", "012345678");
return 0;
} catch (std::exception const & ex) {
std::cout << "Exception: " << ex.what() << std::endl;
return -1;
}
}