The "two primes condition" follows from the fact that columns 4 and 5 have at most one prime, columns 2 has no prime, so there must be at least one prime in columns 1 and 3. But if digit 1 is 8, then digit 3 is 9, so no prime. This will directly create all solutions w/o any test, based on the implied order and your logic above:

use strict;
use warnings;
for my $two (0..1) {
  for my $five (($two+1)..2) {
    for my $one ((3*$five+1)..7) {
      print "$one$two".($one+1).(2*$five)."$five\n";
    }
  }
}
[download]