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.