c# - A Star Search Algorithm -

here have query regarding star search algorithm. i'm building known 8 piece puzzle. game 9 places (1 empty) , have arrange tiles in correct order meet goal position.

i need verify have written algorithm correctly can seek elsewhere in code issue.

i believe algorithm correct because able solve first pre-set puzzle have created requires 1 move reach goal position. however, unable solve puzzles require more moves.

i've tried work in 3 different ways , bring same issue.

attempt 1:

while (openlist.count() > 0)         {             puzzlenode currentnode;             var orderedopenlist = openlist.orderby(puzzlenode => puzzlenode.getpathcost());              currentnode = orderedopenlist.first();             if (compare(currentnode.getpuzzle(), goalarray) == true)             {                 //openlist.removeat(0); //poll                 break;                 // otherwise push currentnode onto closedlist & remove openlist             }             else             {                 openlist.remove(currentnode);                 closedlist.add(currentnode);             }              //generate neighbor nodes             generatesuccessors(currentnode, templist);              (int = 0; < templist.count(); i++)             {                 puzzlenode tempnode = templist[i];                  //skip node if it's in closed list                 if (closedlist.contains(tempnode))                 {                     continue;                 }//end if                  //we need ensure g have seen here shortest 1                 int gscore = currentnode.getg() + 1;                  if (!openlist.contains(tempnode) || gscore < tempnode.getg())                 {                     tempnode.setparentnode(currentnode);                     tempnode.seth(tempnode.calch(currenthueristic, tempnode.getpuzzle(), goalarray));                     tempnode.setg(gscore);                     tempnode.updatepathcost();                      if (!openlist.contains(tempnode))                     {                         openlist.add(tempnode);                     }//end if                   }//end if             }//end          }//end while 

attempt 2:

while (openlist.count() > 0)         {             puzzlenode currentnode = getbestnodefromopenlist(openlist);              openlist.remove(currentnode);             closedlist.add(currentnode);              generatesuccessors(currentnode, templist);              foreach (puzzlenode successornode in templist)             {                 if (compare(successornode.getpuzzle(), goalarray) == true)                 {                     //goto thebreak;                     return successornode;                 }                 successornode.setg(currentnode.getg() + 1);                 successornode.seth(successornode.calch(currenthueristic, successornode.getpuzzle(), goalarray));                 successornode.updatepathcost();                   if (openlisthasbetternode(successornode, openlist))                     continue;                  openlist.add(successornode);             }         }//end while  private static puzzlenode getbestnodefromopenlist(ienumerable<puzzlenode> openlist)     {         return openlist.orderby(n => n.getpathcost()).first();     }  private static bool openlisthasbetternode(puzzlenode successor, ienumerable<puzzlenode> list)     {         return list.firstordefault(n => n.getg().equals(successor.getg())                 && n.getpathcost() < successor.getpathcost()) != null;     } 

attempt 2 alteration of algorithm found on internet: solving 8-puzzle problem

however done best follow psuedocode on wikipedia:

function a*(start,goal)      closedset := empty set    // set of nodes evaluated.      openset := {start}    // set of tentative nodes evaluated, containing start node      came_from := empty map    // map of navigated nodes.       g_score[start] := 0    // cost start along best known path.      // estimated total cost start goal through y.      f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)       while openset not empty          current := node in openset having lowest f_score[] value          if current = goal              return reconstruct_path(came_from, goal)           remove current openset          add current closedset          each neighbor in neighbor_nodes(current)              tentative_g_score := g_score[current] + dist_between(current,neighbor)              if neighbor in closedset                  if tentative_g_score >= g_score[neighbor]                      continue               if neighbor not in openset or tentative_g_score < g_score[neighbor]                   came_from[neighbor] := current                  g_score[neighbor] := tentative_g_score                  f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)                  if neighbor not in openset                      add neighbor openset 

i ask whether can find issue because i'm confused why work 1 of puzzles. only seperate these puzzles amount of moves needed solve goal state.

i've debugged hours , can't see it, can't see else in code have issue. guess i'm asking, correct you?

any questions sure ask , i'll provide more information possible! thank in advance!

note: i'm using custompriorityqueue class (written itowlson) can find here

so here use priorityqueue arrange problem states heuristic value

here simple a* template in c# illustrate how a* search works:

void enqueueall(custompriorityqueue<puzzlenode> a, arraylist<puzzlenode> b) {     foreach(puzzlenode c in b) a.enqueue(c, h(c)); }  // a* heuritic: h = f + g ; h <= h* int h(puzzlenode n);  // returns true if n solution bool issolution(puzzlenode n);  // expand n list of neighbors arraylist<puzzlenode> expand(puzzlenode n);  puzzlenode astar(puzzlenode startpoint) {     custompriorityqueue list = new custompriorityqueue<puzzlenode>();     puzzlenode current = null;      list.enqueue(startpoint, h(startpoint));      while (list.size() > 0)     {         current = list.dequeue();          if (issolution(current))         {             return current;         }          enqueueall(list, expand(current));     } } 

hope helps