For the test cases (ironically, the only difficult ones) it finds the solution for 1 basically instantly, 2 in 0.2 seconds, and checks all possibilities for 3 in about 18 seconds before rejecting it.

For the thousand ‘puzzle’ cases, about half are rejected since the area is simply too small for the presents in an instant. A possible solution is found for all of them in about 80 seconds, so about five per second.

I was concerned that the puzzle cases were about four times the area, and some of them had 255 presents (which might be the maximum stack depth in some languages - not C++, though). So maybe some of them would find a solution quickly, and excluding the worst might take ~ 4 times the size * 30 times the presents * 20 seconds = the best part of an hour. Multithreading it and hoping not too many of them were ‘worst case’, and I could leave my computer on overnight number-crunching it. Box packing is NP-complete and we need a ‘true’ answer rather than an approximation, so I couldn’t see any better way of doing it than checking every possibility. Sorting the list didn’t really show any evidence of puzzles that could be ‘pruned’ - areas that were the same but with increasing numbers of presents, say, so that you could reject the larger ones after the first failure.

Was kicking myself when it ran so quickly.