A* 8-puzzle problem worst case memory usage
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.