A* 8-puzzle problem worst case memory usage We are testing the A* algorithm with Hamming and Manhattan on the 8-puzzle (and its natural generalization n-puzzle) problem.
We have to answer the following question but I can't figure out what it should be.

Our assignment is derived from this. 


  How many board positions are in worst case in memory in function of board size N (where N is the side of a board of size NxN). Give a as low as possible upper bound. You can assume that a board configuration is never in the priority queue several times.


I was thinking about N^2! but that is impossible because not every board position can be reached.
Since the number of possible positions is quite low when N = 3 (9! / 2 = 181,400), you can do an exhaustive search to find the worst case. Check the result, and maybe it leads to some insight.