Write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.
Your goal is to rearrange the blocks so that they are in order, using as few moves as possible. You are permitted to slide blocks horizontally or vertically into the blank square.
Performance requirements.
Your implementation should support all Board methods in time proportional to n2 (or better) in the worst case.