Note that you can cut the time in half or there abouts by adding just two simple checks; this version of your program runs in 6.1 seconds on my machine - the original without the initial 9-digit loop takes 13 seconds on my machine:

use Algorithm::Loops qw( NextPermuteNum );

my @digs= (1..9);
my @map;
@map[1..9]= reverse 1..9;

my $prev= 0;
for my $len ( reverse 1..8 ) {
    do {
        my $num= substr( join( '', @map[ @digs ] ), 0, $len );
        if( $num != $prev and $num !~ /[2468].*[13579]$/ and $num !~ /
+5./) {
            for( $num =~ /./g, 0 ) {
                die "$num\n"   if  ! $_;
                last   if  0 != $num % $_;
            }
        }
        $prev= $num;
    } while( NextPermuteNum(@digs) );
}
[download]

Note that all I've done is add two regex tests - that you don't have any even digits if the last digit is odd, and that you never have a 5 in any but the last position.

Reducing the search space is almost always a good idea.

@/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/;
map{y/X_/\n /;print}map{pop@$_}@/for@/
[download]