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.

  • $\begingroup$ @Principis: Websites disappears. When the linked site disappears, your question makes no sense whatsoever anymore. PS. Sam Loyd claimed to have invented it, but he didn't. $\endgroup$ – gnasher729 Apr 29 '18 at 14:08
  • $\begingroup$ @gnasher729 what do you suggest to change it to? The 8-puzzle problem is pretty standard as far as I know. I mean I can't copy the whole assignment here because it's not in English and itś very long. $\endgroup$ – Principis Apr 29 '18 at 15:15
  • $\begingroup$ I've never, ever heard of it under the name. Actually, you could buy cheap plastic toys for what you would call the "15-puzzle" (haven't seen them in years), but I've never heard of either "15-puzzle" nor "8-puzzle". $\endgroup$ – gnasher729 Apr 29 '18 at 17:21

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.