A simple solution is to sort the numbers, then place the greatest n numbers on the main diagonal. The other numbers can be placed in any order.

C++ solution (Marius Gavrilescu)

    1 #include <cstdio>
    2 #include <algorithm>
    3 #include <functional>
    4 
    5 int v[10005];
    6 
    7 int main(void){
    8     int n;
    9     scanf("%d", &n);
   10     for(int i = 0 ; i < n * n ; i++)
   11         scanf("%d", v + i);
   12     std::sort(v, v + n * n, std::greater<int>());
   13 
   14     int p = n;
   15     for(int i = 0 ; i < n ; i++) {
   16         for(int j = 0 ; j < n ; j++)
   17             printf("%d ", i == j ? v[i] : v[p++]);
   18         puts("");
   19     }
   20     return 0;
   21 }

Perl soluton (Marius Gavrilescu)

    1 #!/usr/bin/perl
    2 use v5.14;
    3 use warnings;
    4 
    5 my $n = <>;
    6 my @v = sort { $b <=> $a } split ' ', <>;
    7 my $p = $n;
    8 
    9 for my $i (1 .. $n) {
   10     for my $j (1 .. $n) {
   11         print $i == $j ? $v[$i - 1] : $v[$p++], ' '
   12     }
   13     say '';
   14 }