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.