I'm sure there's a chapter on the 15-puzzle etc in "Chips Challenging Champions" by Schaeffer and Herik (2002), but regret I can't lay hands on my copy at the moment. http://www.cs.ualberta.ca/~joe/Abstracts/15puzzle.html This paper by Culberson and Schaeffer (1996) is available on the web, refers to A*-searching, and says that they reduced the computational effort 1000-fold with their method. g