Well, blokhead's memoize version take < 10s so that the easiest thing available as a benchmark and it's takes little effort to run it.
I managed to generate all solutions just using Perl in 74 mins on one machine and 2 hours on another. I'd like to be able to compare these results to your 72 mins without having to chew 72 mins of CPU. I just tried it on that machine and killed it after 93 mins. It was compiled with -O2. Have you got a very very fast machine? If so then I think Perl with ugly-memoize beats the C, which is very surprising.