Beam search and A* search for solving puzzles in Arduino

I recently started a topic on implementing the 8-puzzle in Arduino, and while this topic uses the same code, it focuses on a different portion of it. The forum rules do not appear to disallow starting multiple topics on the same project, but if a forum admin deems it necessary they should merge this into my other topic. I've finished implementing the 8-puzzle, and am now having trouble with the beam search function. What I want to do is, when a solution has been found by the algorithm, it backtracks and prints the steps that led to that solution.
Here's the code (some functions have been omitted due to the forum's character limit):

int AposTemp=0; //position of the tile that moves to replace 'b'
int dir=0; //direction of move - up, down, left, right
String action="Sample Text"; //input variable by user

boolean isValid=true; //checks if dir is a possible move
boolean repeat=true; //if not, restarts function
boolean canSearch=true; //checks if max nodes exceeded, stops search if so
boolean started=false;//checks if nodes have been expanded yet
boolean finished=false;//checks if solution has been found
int heur=0; //value of heuristic algorithm (of either type)
int type=1; //which heuristic to use
int k=3;
int l=0;

int puzzle[9];
int Xpos[9];
int Goal[9]={0,1,2,3,4,5,6,7,8};
int movesList[100];
int heurtemp[4][2];
int possibledirs[4];//list of valid moves, out of a possible 4
int queue[4][11];

int numNodes=0;

void printState(){
  for (int g=0;g<9;g++){
    if(puzzle[g]!=0){
      Serial.print(puzzle[g]);
    }
    else{
      Serial.print("b");
    }
    if((g==2)||(g==5)||(g==8)){
      Serial.println();
    }
  }
}

void heuristic(int type){//checks number of tiles not in goal state
  if (type==1){//
    for(int j=0;j<10;j++){
      if(Goal[j]!=Xpos[j]){
        heur+=1;
      }
    }
  }
  if(type==2){//linear distance between tile and goal state
    int diff[8];
    int MovesX[8];
    int MovesY[8];
    double Distance[8];

    for(int i=0;i<10;i++){
      diff[i]=abs(Goal[i]-Xpos[i]);
      MovesX[i]=diff[i]-(3*MovesY[i]);
      MovesY[i]=round((diff[i]/3)-0.5); //0.5 subtracted to make it round down
      Distance[i]=pow((pow(MovesX[i],2) + pow(MovesY[i],2)),0.5);//distance formula
      heur+=Distance[i];
    }
  }
}

void Change (int dir){
  isValid=true;
  if ((Xpos[0]==0)||(Xpos[0]==3)||(Xpos[0]==6)){//left not valid move
    if(dir==1) isValid=false;
  }  
  if ((Xpos[0]==2)||(Xpos[0]==5)||(Xpos[0]==8)){//right not valid move
    if(dir==2) isValid=false;
  }
  if ((Xpos[0]==0)||(Xpos[0]==1)||(Xpos[0]==2)){//up not valid move
    if(dir==3) isValid=false;
  }
  if ((Xpos[0]==6)||(Xpos[0]==7)||(Xpos[0]==8)){//down not valid move
    if(dir==4) isValid=false;
  }
  
  if (isValid==true){
    if (dir==1){
      AposTemp=puzzle[Xpos[0]-1];
      puzzle[Xpos[0]]=AposTemp;
      puzzle[Xpos[0]-1]=0;
      Xpos[0]--;
    }
    if (dir==2){
      AposTemp=puzzle[Xpos[0]+1];
      puzzle[Xpos[0]]=AposTemp;
      puzzle[Xpos[0]+1]=0;
      Xpos[0]++;
    }
    if (dir==3){//up
      AposTemp=puzzle[Xpos[0]-3];
      puzzle[Xpos[0]]=AposTemp;
      puzzle[Xpos[0]-3]=0;
      Xpos[0]-=3;
      
    }
    if (dir==4){//down
      AposTemp=puzzle[Xpos[0]+3];
      puzzle[Xpos[0]]=AposTemp;
      puzzle[Xpos[0]+3]=0;
      Xpos[0]+=3;
    }
    printState();
    repeat=false;
  }
  else{
    repeat=true;
  }
}

void checkMove(int dir){
  if ((Xpos[0]==0)||(Xpos[0]==3)||(Xpos[0]==6)){//left not valid move
    if(dir==1) isValid=false;
  }  
  else{
  if ((Xpos[0]==2)||(Xpos[0]==5)||(Xpos[0]==8)){//right not valid move
    if(dir==2) isValid=false;
  }
  else{
  if ((Xpos[0]==0)||(Xpos[0]==1)||(Xpos[0]==2)){//up not valid move
    if(dir==3) isValid=false;
  }
  else{
  if ((Xpos[0]==6)||(Xpos[0]==7)||(Xpos[0]==8)){//down not valid move
    if(dir==4) isValid=false;
  }
  else{
    isValid=true;
  }
  }
  }
  }
}

void randomizeState(int n){
  int randommove;
  for(int f=n;f>0;f--){
    repeat=true;
    while(repeat==true){
    randommove = round(random(100,500)/100);
    Change(randommove);
    }
    Serial.println("Direction: " + String(randommove));
  }
}

void solvebeam(int k){
  boolean expandNode=false;
  int queue[k][11];//movelist stored, with positions and heuristics
    while(heur>0){
      if(started==false){//starting from randomizeState[]
        for(int a=0;a<9;a++){
          queue[0][a]=Xpos[a];//sets initial state
        }
        expandNode=true;
        started=true;
      }
      else{//starting from k preset nodes
      for (int d=0;d<(k+1);d++){
        for (int b=0;b<10;b++){
          Xpos[b]=queue[d][b];
          expandNode=true;
          }
        }
      }
      if(expandNode==true){  
        for(int o=0;o<4;o++){
          for(int m=1;m<5;m++){//stores what moves can be made and what can't
            checkMove(m);
            possibledirs[m]=isValid;
            if(possibledirs[m]==true){
              l++;
              Change(m);
              heuristic(type);
              for(int r=0;r<10;r++){
                heurtemp[o][r]=Xpos[r];
              }
              heurtemp[o][10]=heur;
              heurtemp[o][11]=m;
              if(m==1) Change(2);//moves back so a different node can be considered
              if(m==2) Change(1);
              if(m==3) Change(4);
              if(m==4) Change(3);
            }
          }
        }
        for(int z=0;z<3;z++){//sorts 2D algorithm according to heuristic
          for(int c=0;c<(4-(z+1));c++){
            if (heurtemp[c][10]>heurtemp[c+1][10]){
            int t[11];
              for(int e=0;e<12;e++){
                t[e]=heurtemp[c][e];
                heurtemp[c][e]=heurtemp[c+1][e];
                heurtemp[c+1][e]=t[e];
              }
            }
          }
        }
        for(int y=0;y<(k+1);y++){//maps the top k values onto the queue for the next round
          for(int f=0;f<12;f++){
            queue[y][f]=heurtemp[y][f];
            if(f<9){
              Xpos[f]=queue[y][f];//temporarily sets position to each of k nodes selected so that printState() can work
            }
          }
          printState();//outputs k selected paths
          Serial.println("Heuristic value: " + heurtemp[y][10]); //keeps track of moves made, heuristic should decrease for increasing queue values
          Serial.println("Direction: " + heurtemp[y][11]);
        }
     }
     expandNode=false;//prevents it from repeating itself
  }      
  if(heur==0){//puzzle solved!
    expandNode=false;
    finished=true;
      //get the node in queue, backtrack to find the solution, print solution
  }
}

void setup(){
  randomSeed(analogRead(A0));
  SetState();
  Serial.begin(9600);
  printState();
  randomizeState(80);
}

void loop(){
  if (Serial.available() > 0) {
    action = Serial.readString();
  }
  if (action=="Solve beam"){
    solvebeam(k);
    action="0";
  }
}

If you find any other errors, let me know. solvebeam() does not appear to work currently, as whenever it is called by the Serial.readString() function it does not do anything.

Figured out that solvebeam() was not doing anything because heuristic() had not been called to start it off. Did that, and got this as an output:

354
628
17b
Direction: 2 //the last move made by randomizeState(80), or the starting position for the algorithm to 'solve' from

When 'Solve beam' was input (k set to 3):

354
628
1b7

354
628
17b

354
628
17b
Heuristic value:
Direction:

354
628
17b
Heuristic value:
ªªªªªªªªªªªªªªª... //this gets printed infinitely

354
628
17b
ªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªª//same for these
ªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªªª

354
628
17b

What are those infinite strings, and where are they coming from? I've never seen them before.

String objects should be avoided in Arduino. Use character arrays ("c-strings") instead.

String operations cause memory problems and as a result, your program is pretty much guaranteed to fail at some point.

Unterminated prints like the above are probably caused by improper termination of a character array, that is, lacking the final zero byte.

int heurtemp[4][2];

          Serial.println("Heuristic value: " + heurtemp[y][10]); //keeps track of moves made, heuristic should decrease for increasing queue values
          Serial.println("Direction: " + heurtemp[y][11]);

A) You are using the 11th and 12th elements of a 2 element array.
B) You are adding that garbage integer to the address of a string constant, indexing off the end of the constant and printing whatever is in memory at that address.