Hello I am working in c++ program. Its about using A* search to find the right p

Question

Hello I am working in c++ program. Its about using A* search to find the right path to solve the 8th puzzle or the" slides puzzle". I have already started but I could not finish. I am stacked!

#include <iomanip>

#include <iostream>

#include <string>

#include <vector>

using namespace std;

enum Move { UP, DOWN, LEFT, RIGHT };

class Puzzle{

public:

Puzzle(vector<int> s){

s[0][0] = -1;

s[0][0] = 1;

s[0][0] = 2;

s[1][0] = 3;

s[1][0] = 4;

s[1][0] = 5;

s[2][0] = 6;

s[2][0] = 7;

s[2][0] = 8;

SetBlank(s);

}

Puzzle(Puzzle & other){

for (int i = 0; i < 3; i++){

for(int j=0; j < 3; j++)

{

p[i][j] = other->s[i];

}

}

}

}

void setBlank(vector <vector<int>>& state){

for(int i = 0; i<3 ; i++){

for(int j=0; j<3; j++){

  if(state[i][j] == -1)

   cout << "_ ";

else

cout << state[i][j] << " ";

cout << endl;

  }

}

}

void Print(){

cout << "Puzzle ---> " << blank_i << ", " << blank_j << endl;

}

bool puzzleMoves ( Moves m) {

//cout << "Move Blank_i: " << blank_i << "blank_j: " << blank_j << endl;

int blank_i=0;

int blank_j=0;

int target_i = blank_i;

int target_j = blank_j;

if (m == RIGHT){

if (blank_j == 0)

return false;

else

target_j++;

}

if(m == LEFT){

if (blank_j == 1)

return false;

else

target_j++;

}

if(m == UP){

if (blank_j == 2)

return false;

else

target_j++;

}

if(m == DOWN){

if(blank_j == 3)

return false;

else

target_j++;

}

}

boolInSet(vector<Puzzle*>){

for(int i = 0; i < (int)puzList.size(); ){

}

}

int main(){

cout << "main start" << endl;

int startints[] = { 7, 2, 4, 5, -1, 6, 8, 3, 1};

int goalints[] = { -1, 1, 2, 3, 4, 5, 6, 7, 8};

int start[2][2]; //start state

start[0][0] = 7;

start[0][1] = 2;

start[0][2] = 4;

start[1][0] = 5;

start[1][1] = -1;

start[1][2] = 6;

start[2][0] = 8;

start[2][1] = 3;

start[2][2] = 1;

SetBlank();

parent = NULL;

int goal[2][2]; //goal state

start[0][0] = -1;

start[0][0] = 1;

start[0][0] = 2;

start[1][0] = 3;

start[1][0] = 4;

start[1][0] = 5;

start[2][0] = 6;

start[2][0] = 7;

start[2][0] = 8;

cout << "Goal puzzle: " << endl;

Puzzle* startPuzzle = new Puzzle(s);

Puzzle* goalPuzzle = new Puzzle(g);

cout << "start puzzle " << endl;

startPuzzle

bool foundSol = false;

Puzzle* goalPuzzleFound = NULL;

int numAttempt = 0;

while(!openSet.empty() && !foundSol){

numAttempt++;

Puzzle* cur = openSet[0];

openSet.erase(openSet.begin()) ;

exploredSet.push_back(cur);

for(int i = 0; i < 4; i++){

move mt;

if(i == 0) mt = RIGHT;

if(i == 1) mt = LEFT;

if(i == 2) mt = UP;

if(i == 3) mt = DOWN;

Puzzle* attempt = new Puzzle(*cur);

cout << "attempt " << numAttempt << ", " << i << endl;

//attempt->Print();

bool validMove = attempt->Move(mt);

bool inExploredSet = InSet(exploredSet, attempt);

bool inOpenSet = InSet(openSet, attempt);

if(validMove && !inOpenSet){

//If valid, move to openset

openSet.push_back(attempt);

if(attempt-> = (goalPuzzle)){

foundSol;

goalPuzzleFound = attempt;

}

}

else

delete attempt;

}

}

if(foundSol){

cout << "The solution to the puzzle has been found!" << endl;

}

public void run() {

int solPath = NSTEMP, nodeMin, i, distance = 255;

Thread me = Thread.currentThread();

try

tracker.waitForID(0);

catch(InterruptedException e){

return;

}

int time = 0;

while(timer == me){

try{

Thread.currentThread().sleep( 1000);

time++;

}

catch(InterruptedException e){

break;

}

expand(UP);

expand(RIGHT);

expand(DOWN);

expand(LEFT);

nodeMin = UP; //debugging

distance = distNode[nodeMin];

for(i = 1; i < EXPTOTAL; i++) {

if(distNode[nodeMin] > distNode[i]){

nodeMin = i;

distance = distNode[nodeMin];

}

}

if((nodeMin % 4) + 2 == solPath){

for(i = 0; i < EXPTOTAL; i++){

if((distNode[i] > distNode[nodeMin]) && (distNode[i] < 255)){

nodeMin = i;

}

}

}

solPath = nodeMin;

//copyNode(PROBLEM, nodeMin);

//repaint();

}

}

}

return 0;

Explanation / Answer

Program :

#include <bits/stdc++.h>
   #include <functional>
using namespace std;  
  
   map<vector<vector<int> > , bool> visited;
   map<vector<vector<int> > , vector<vector<int> > > part;
   vector<vector<int> > number(3,vector<int> (3));
  
   bool visit(vector<vector<int> > v)
   {
       if(visited[v]==true)
           return true;
       else
           return false;
   }
  
   int manhattan(vector<vector<int> > v , int moves)
   {
       int distance=moves;
       for(int i=0;i<3;i++)
       {
           for(int j=0;j<3;j++)
           {
               if(v[i][j]!=0)
               {
                   for(int k=0;k<3;k++)
                   {
                       for(int l=0;l<3;l++)
                       {
                           if(v[i][j]==number[k][l])
                               distance+=abs(i-k)+abs(j-l);
                       }
                   }
               }
           }
       }
      
       return distance;
   }
  
   bool isNumber(vector<vector<int> > v)
   {
       for(int i=0;i<3;i++)
       {
           for(int j=0;j<3;j++)
           {
               if(v[i][j]!=number[i][j])
                   return false;
           }
       }
  
   return true;
   }
  
   bool safe(int i,int j)
   {
       if(i>=0 && i<=2 && j>=0 && j<=2)
       return true;
       else
       return false;
   }
   int px[]={-1,+1,0,0};
   int py[]={0,0,-1,+1};
   vector<vector<vector<int> > > neigh(vector<vector<int> > a)
   {
       pair<int,int> pos;
       for(int i=0;i<3;i++)
       {
           for(int j=0;j<3;j++)
           {
               if(a[i][j]==0)
               {
                   pos.first=i;
                   pos.second=j;
                   break;
               }
           }
       }
       vector<vector<vector<int> > > ans;
       for(int k=0;k<4;k++)
       {
           int qx = pos.first;
           int qy = pos.second;
           vector<vector<int> > n = a;
           if(safe(qx+px[k],qy+py[k]))
           {
               swap(n[qx+px[k]][qy+py[k]],n[qx][qy]);
               ans.push_back(n);
           }
       }
  
   return ans;
   }
          
   typedef pair<vector<vector<int> > , int> state;
  
   struct compare
   {
       bool operator() (state &a, state &b)
       {
           int pq = manhattan(a.first,a.second);
           int xy = manhattan(b.first,b.second);
           return pq<xy;
       }
   };
  
   void path(vector<vector<int> > s)
   {
   if(part.count(s))
   path(part[s]);
     
   for(int i=0;i<3;i++)
   {
       for(int j=0;j<3;j++)
       {
           printf("%d ",s[i][j]);
       }
       cout<<endl;
   }
     
   cout<<endl;
   return;
   }
  
   void sol(vector<vector<int> > s)
   {
       for(int i=0;i<3;i++)
   {
       for(int j=0;j<3;j++)
       {
           printf("%d ",s[i][j]);
       }
       cout<<endl;
   }
   }
  
   void solution(vector<vector<int> > v, int moves)
   {
      
       priority_queue<state,vector<state>,compare > Q;
       Q.push(state(v,moves));
       while(!Q.empty())
       {
           vector<vector<int> > s = Q.top().first;
           Q.pop();
          
           visited[s]=true;
          
           if(s==number)
           {
              
               path(s);
               break;
           }
           vector<vector<vector<int> > > ns = neigh(s);
           vector<vector<vector<int> > >::iterator it;
          
           for(it=ns.begin();it!=ns.end();it++)
           {
               vector<vector<int> > temp = *it;
               if(!visit(temp))
               {
                   part.insert(pair<vector<vector<int> > , vector<vector<int> > >(temp,s));
                   Q.push(state(temp,moves+1));
               }
           }
       }
       return;
   }
  
   int main()
   {
       vector<vector<int> > v(3,vector<int> (3));
       for(int i=0;i<3;i++)
       {
           for(int j=0;j<3;j++)
           {
               cin>>v[i][j];  
           }
       }
      
       number[0][0] = 3;
       number[0][1] = 0;
       number[0][2] = 2;
       number[1][0] = 5;
       number[1][1] = 4;
       number[1][2] = 8;
       number[2][0] = 1;
       number[2][1] = 6;
       number[2][2] = 7;
      
       solution(v,0);
   }
  
  
  
Output :

3 0 2

5 4 8

1 6 7

0 3 2

5 4 8

1 6 7

5 3 2

0 4 8

1 6 7

5 3 2

4 0 8

1 6 7

5 3 2

4 6 8

1 0 7

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.