XPost: comp.ai.games   
   From: wilson.max@gmail.com   
      
   Bhavesh,   
      
   That works okay for a puzzle this small (9^4 tries max?) but what if   
   it's 4x4 or 5x5? Instead of strictly breadth-first search, why not   
   branch-and-bound? Especially if he's doing this for practice at larger   
   things.   
      
   Key idea: instead of ordering the proposed solutions by # of moves made   
   to get to this point, order by h = number of moves up to this point +   
   g^ = estimated number of moves to finish puzzle, where g is an   
   estimator function of g = optimal number of moves to finish puzzle from   
   this position, chosen such that g >= g^. (g^ is an optimistic   
   estimate.) In this case, a simple estimator function is sum(# of places   
   each tile is removed from its "correct" position). IIRC, this will   
   produce the same answer as Bhavesh's algorithm but will arrive at the   
   answer faster.   
      
   Keywords: branch-and-bound, dynamic programming.   
      
   Max Wilson   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)