depth first search - Java: Solving 15 Puzzle using Fitness functions -

i working on project solve 15 puzzle using fitness functions. there 3 kinds of fitness functions can used,

1. fitness function1= 1 - (number of misplaced tiles/total number of tiles);
2. fitness function2= 1- (sum of distances of misplaced tiles goal position/64)
3. fitness function3= (fitness 2+ fitness 1 )/2

the solver meant search possible moves improves fitness function value until whole puzzle board solved (where fitness function=1). stocked while trying generate moves because solver print unsuccessful search routes along actual route e.g. w,s,w,n,s,n,s,n,s,n,s,n,s,n,s,n,s,n ( in reverse order) , means nwsw. solver searches , forth several times , prints unwanted routes. want exclude visited locations in recursion , print valid moves , not unsuccessful moves. code available below:

<pre><code> enter code here  package definitions;  public class puzzle { public treenode boardstree; public boolean searching; public int lastpos;   puzzle(board b) {  boardstree = new treenode(b);  lastpos = b.blank_pos; }  public string solver(board b, string route, int level, double fitval){ //system.out.println("route in level " + level +": " +route + " fitness: ");                           //system.out.print(b.f1.getfitnessval());  //if depth of tree level 15 or board solved return route(moves e.g. wns) if(level == 15||b.solved){ //if(route != ""){ //if(route.length()>1){ // return route.substring(0, route.length()-1); //}else{ return route; //} }else{ //create temporary store last position  //create 4 auxilliary puzzle boards has child puzzles //perform different moves on blank space on each board in different directions       //(n=0,s=1,e=2,w=3) lastpos = b.blank_pos; board auxn = new board(4,b.tileslist); board auxs = new board(4,b.tileslist); board auxe = new board(4,b.tileslist); board auxw = new board(4,b.tileslist); //builds tree  //moves north //b.isvalidmove(north=0,south=1,east=2,west=3) if( b.isvalidmove(0)){   //if lastposition (blankposition in parent board) not position of    //cell in north moveblank north  if(lastpos != (lastpos - 4)){  auxn.moveblank(0);  boardstree.addson(0,auxn);  if(fitval > boardstree.getson(0).getstate().f1.getfitnessval()){   auxn.print();   searching = false;   return route + "n";      }    }   }  //moves south //b.isvalidmove(north=0,south=1,east=2,west=3) if( b.isvalidmove(1) ){   //if lastposition (blankposition in parent board) not position of    //cell in north moveblank north if(lastpos != (lastpos + 4)){  auxs.moveblank(1);  boardstree.addson(1,auxs);  if(fitval > boardstree.getson(1).getstate().f1.getfitnessval()){   auxs.print();   searching = false;   return route + "s";     }   }  }   //moves east  if( b.isvalidmove(2) ){     if(lastpos != (lastpos + 1)){        auxe.moveblank(2);        boardstree.addson(2,auxe);        if(fitval > boardstree.getson(2).getstate().f1.getfitnessval()){        auxe.print();        searching = false;        return route + "e";      }     }    }  //moves west if( b.isvalidmove(3) ){  if(lastpos != (lastpos -1)){  auxw.moveblank(3);  boardstree.addson(3,auxw);  if(fitval > boardstree.getson(3).getstate().f1.getfitnessval()){   auxw.print();   searching = false;   return route + "w";    }  } }  //evaluate new states  if(searching && b.isvalidmove(0)){   system.out.println("actual: " +auxn.blank_pos+ " previo: "+lastpos );   if(lastpos != auxn.blank_pos){      lastpos = auxn.blank_pos;      route = solver(auxn,route + "n", level+1, fitval); //north      }else{      //if  solution not generated enter recursion find further solutions @          //further depth of tree      solver(auxn,route, level+1, fitval); //north           }  }  if(searching  && b.isvalidmove(1)){   //system.out.println("actual: " +auxs.blank_pos+ " previo: "+lastpos );   if(lastpos != auxs.blank_pos){     lastpos = auxs.blank_pos;     route =solver(auxs,route + "s", level+1, fitval); //north   }else{     solver(auxs,route, level+1, fitval); //north       }  }  if(searching  && b.isvalidmove(2)){    //system.out.println("actual: " +auxe.blank_pos+ " previo: "+lastpos );    if(lastpos != auxe.blank_pos){    lastpos = auxe.blank_pos;    route = solver(auxe,route + "e", level+1, fitval); //north    }else{    solver(auxe,route, level+1, fitval); //north         }    }    if(searching  && b.isvalidmove(3)){     //system.out.println("actual: " +auxw.blank_pos+ " previo: "+lastpos );      if(lastpos != auxw.blank_pos){      lastpos = auxw.blank_pos;      route =solver(auxw,route + "w", level+1, fitval); //north      }else{      solver(auxw,route, level+1, fitval); //north            }       }      }      return route;       }      }