Question

Apply the A" algorithm to the 8-puzzle problem to the initial tile pattern shown below to arrive at the goal node. Show expansion of the tiles as illustrated in lecture notes and book chapter, along with evaluation value f g+h, numeric order of selected nodes and backtracking arrows Numeric order of chosen node #of search bles where n is a node 47 displaced nitial node 81 Goal node 12 5 8 13 7 4 3 6 2 5 6 25 What's next? 17 245 813 8 1.3 7 4 5 8 1.3 8 113 2 4 When the f g + h of a row are equal, choose either the left or right tile.

Answer 1

#include <bits/stdc++.h>
using namespace std;

class state {

public:
   int board[3][3];
   int g,h;

   state *came_from;

  
   state() {
       g=0;
       h=0;
       came_from = NULL;
   }
   void print() {
       for(int i=0;i<3;i++) {
           for(int j=0;j<3;j++)
               cout<<board[i][j]<<" ";
           cout<<endl;
       }
       printf("g: %d, h:%d\n",g, h);
       int eval = h - g;
       printf("heuristic value : %d \n\n", eval);
   }
  
  
   bool operator ==(state a) {
       for(int i=0;i<3;i++)
           for(int j=0;j<3;j++)
               if(this->board[i][j] != a.board[i][j])
                   return false;
       return true;
   }

  
};

int heuristic(state current,state goal) {
   int distance=0;
   for(int i=0;i<3;i++)
       for(int j=0;j<3;j++)
           if(current.board[i][j] != goal.board[i][j])
               distance++;
   return distance;
}

vector<state> output;

bool smallerH(state a,state b) {
   return a.h < b.h;
}

void swap(state &a,int i,int j,int posi,int posj) {
   int temp;
   temp = a.board[i][j];
   a.board[i][j] = a.board[posi][posj];
   a.board[posi][posj] = temp;
}

bool isInSet(state a,vector<state> b) {
   for(int i=0;i<b.size();i++)
       if(a == b[i])
           return true;

   return false;
}

void addNeighbor(state current,state goal, int newI, int newJ, int posi, int posj,
                   vector<state> &openset,vector<state> closedset) {
                  
   state newstate = current;
   swap(newstate,newI,newJ,posi,posj);
       if(!isInSet(newstate,closedset)) {

           int tentative_g_score = current.g + 1;

           if( !isInSet(newstate,openset) || tentative_g_score < newstate.g ) {

               newstate.g = tentative_g_score;
               newstate.h = newstate.g + heuristic(newstate,goal);
  
state *temp = new state();
*temp = current;
               newstate.came_from = temp;
               openset.push_back(newstate);
           }
       }
}

void neighbors(state current,state goal, vector<state> &openset,vector<state> closedset) {
   int i,j,posi,posj;
  
   //Find the position of '0'
   for(i=0;i<3;i++){
       for(j=0;j<3;j++) {
           if(current.board[i][j] == 0)
           {
               posi=i;
               posj=j;
           }
       }  
   }
   i=posi; j=posj;

   if((i-1)>=0) {
       i--;
       addNeighbor(current,goal,i,j,posi,posj,openset,closedset);
   }
  
   if((i+1)<3) {
       i++;
       addNeighbor(current,goal,i,j,posi,posj,openset,closedset);
   }

   if((j-1)>=0) {
       j--;
       addNeighbor(current,goal,i,j,posi,posj,openset,closedset);
   }
  
   if((j+1)<3) {
       j++;
       addNeighbor(current,goal,i,j,posi,posj,openset,closedset);
   }
}

void reconstruct_path(state current, vector<state> &came_from) {
state *temp = &current;
while(temp != NULL) {
came_from.push_back(*temp);
temp = temp->came_from;
}
}

bool astar(state start, state goal) {
   vector<state> closedset;
   vector<state> openset;

   state current;

   start.g = 0;
   start.h = start.g + heuristic(start,goal);

   openset.push_back(start);
  
   while(!openset.empty()) {

       sort(openset.begin(),openset.end(),smallerH);

       current = openset[0]; //select the state having lowest fscore value.
      
       if(current == goal) {
           reconstruct_path(current,output);
           return true;
       }

       openset.erase(openset.begin());
       closedset.push_back(current);

       neighbors(current,goal,openset,closedset);
   }

   return false;
}

int main() {
   state start,goal;
  
   cout<<"Enter the 3x3 starting position of the board :\n";
   for(int i=0;i<3;i++)
       for(int j=0;j<3;j++)
           cin>>start.board[i][j];

   cout<<"Enter goal board :\n";
   for(int i=0;i<3;i++)
       for(int j=0;j<3;j++)
           cin>>goal.board[i][j];

   if(astar(start,goal) == true) {
for(int i=output.size()-1;i>=0;i--) {
output[i].print();
}
cout<<"Successful in finding out the goal state. \n";
   }
   else
       cout<<"\n Not able to find the goal state. \n";
   return 0;
}

This would be the solution what you are looking for. You can find the proper code on my github as well from which this has been taken and adjusted as per your requirement.

Cheers.