It looks like exponential-order to me. I added some code to sum up the number of permutations of the sets:
$bigtotal += Math::NumberCruncher::Permutation(scalar(@Num),MATRIX_D
Here are the results:
Maximum divisor is 416, solution is 2496-9152-1664-2080
Checked 19301184 cases
1445.940u 5.500s 27:10.91 88.9% 0+0k 0+0io 364pf+0w
Maximum divisor is 44, solution is 132-792-660
Checked 140526 cases
10.690u 0.050s 0:14.69 73.1% 0+0k 0+0io 364pf+0w
Order 2:Maximum divisor is 7, solution is 21-84
Checked 820 cases
0.290u 0.010s 0:00.33 90.9% 0+0k 0+0io 364pf+0w
At that rate, order 5 will test about 1 billion cases and take over a day to run. But
I think it might be feasible if bad solution sets are eliminated early.
The big problem is the permutations, which are factorial order. I would suggest picking the corner two items first. They have to have the same top digit. Then that determines the possible top digits of the rest of the rows.