Solving a more general version of the 15-puzzle.

To solve the N x N puzzle, reduce it to the N-1 x N-1 puzzle: Get the
top row in order, then the remaining part of the left column, and
never touch them again. Repeat the same process recursively, until you
reach the base case of a 1 x 1 puzzle. You will still need to use the
various heuristics and A* search, but now the search is much more
focused. 

This idea is mentioned in
        Jackson, P.C., Jr., Introduction to Artificial Intelligence.
        New York: Petrocelli Books, 1974.
as being originated by A.K. Chandra, and is also discussed in Nilson's AI book
as an example of searching using mileposts.