First thing you do is delete from your %dictionary all ur-words that contain any letters not present in your source phrase. Another preprocess you can do is eliminate all ur-words that are already too long.

my $source_phrase = 'perl wisdom';
my $source_urword = join '', grep /\w/, sort_uniq( split //, $source_p
+hrase ); # or whatever

for ( keys %dictionary ) {
    delete $dictionary{$_}  if 
        /[^$source_urword]/ ||
        length($_) > length($source_urword);
}
[download]

That should significantly enhance the performance of any subsequent algorithm... unless you're unlucky enough to have a source phrase containing nearly all the available alphabet.