I was shown those three problems the other day on http://www.itasoftware.com/careers/programmers.php, and spent a decent amount of time solving them. My solution for 9 nines ran in about 15 seconds on my celeron system here. I've also answered the other two problems, and was verified by the CTO of ITA Software for all 3. 
#!/usr/bin/perl
use strict;
use Data::Dumper;
$|++;


my %PossibleTotals = ();
%{$PossibleTotals{1}} = (9, "9");
%{$PossibleTotals{2}} = (9+9, "(9+9)", 9-9, "(9-9)", 9*9, "(9*9)", 9/9
+, "(9/9)");

foreach my $WhichNine (3..9) {
    print "Working $WhichNine\n";
    for (my $Count = 1; $Count <= $WhichNine / 2; $Count++) {
#         print "Doing $Count, $WhichNine - $Count\n";
         foreach my $Column1 (keys %{$PossibleTotals{$Count}}) {
             foreach my $Column2 (keys %{$PossibleTotals{$WhichNine - 
+$Count}}) {
                 ${$PossibleTotals{$WhichNine}}{$Column1 + $Column2} =
+ 
                   "(" . ${$PossibleTotals{$Count}}{$Column1} . "+" . 
+${$PossibleTotals{$WhichNine - $Count}}{$Column2} . ")";
                 ${$PossibleTotals{$WhichNine}}{abs($Column1 - $Column
+2)} = 
                   "(" . ${$PossibleTotals{$Count}}{$Column1} . "-" . 
+${$PossibleTotals{$WhichNine-$Count}}{$Column2} . ")";
                 ${$PossibleTotals{$WhichNine}}{$Column1 * $Column2} =
+ 
                   "(" . ${$PossibleTotals{$Count}}{$Column1} . "*" . 
+${$PossibleTotals{$WhichNine-$Count}}{$Column2} . ")";
                 ${$PossibleTotals{$WhichNine}}{sprintf("%.15f", $Colu
+mn1 / $Column2)} =
                   "(" . ${$PossibleTotals{$Count}}{$Column1} . "/" . 
+${$PossibleTotals{$WhichNine-$Count}}{$Column2} . ")" if ($Column2 !=
+ 0);
                 ${$PossibleTotals{$WhichNine}}{sprintf("%.15f", $Colu
+mn2 / $Column1)} = 
                   "(" . ${$PossibleTotals{$WhichNine-$Count}}{$Column
+2} . "/" . ${$PossibleTotals{$Count}}{$Column1} . ")" if ($Column1 !=
+ 0);
             }
         }
     }
}


print "finished calculating\n";
my (@FoundNumbers) = ();
my %TempHash = ();
foreach (keys %{$PossibleTotals{9}}) {
    {$TempHash{int($_)} = 1 if (($_ < 10000) && (int($_) == sprintf("%
+.7f", $_)));
     print "$_ : ${$PossibleTotals{9}}{$_}\n" if $_ =~ /^19[45]\./;
}
(@FoundNumbers) = sort {$a<=>$b} keys (%TempHash);
my $Count = 0;

while (@FoundNumbers) {
    my $Number = shift(@FoundNumbers);
    if (($Count == $Number) && (${$PossibleTotals{9}}{$Number} =~ /[9\
+D]{9}/g)) {
        print "$Number = " .${$PossibleTotals{9}}{$Number} . "\n";
    } else {
        print "The first number missed is $Number\n";
        last;
    }
    $Count++;
}

[download]

In reply to As per Tilly, The 9 nines solution by dfog

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.