More ideas on problem 2.5. This discusses something I have mentioned only in passing. A* search is an AI term for a kind of search midway between Breadth First and Best First. The idea is to use a priority based on two parts: the the AI lingo, the priority function is f*, where
f*(b) = g*(b) + h*(b) where h*(b) is the best evaluation function we can come up with (say distance to the center), and g*(b) is the best estimate of the number of steps required to reach this position. You may find you reach a position that took you 20 steps through another path that only takes 16 steps, so g*(b) is just an estimate. But when you find the better path, you update the stored board to point to the new, better, solution, which has the effect of lowering g*(b), and thus f*(b), and thus improving the priority of the position. Breadth first amounts to f*(b) = g*(b) and Best first amounts to f*(b) = h*(b) While Breadth first will find the minimal solution, it is very slow. A* search also finds the minimal solution, but does so more rapidly, by focusing on those positions that lead someplace (have a low h*()). Other combinations of g and h are possible, trading speed for accuracy. I find A* search a simple change to make which results in shorter solutions. (One question: when you update a board, how do you reflect it's new cost in boards that descend from that position? Does it matter?) My resource was the Handbook of AI, but Winston's AI book also discusses A* search. - jeff parker