乱択解法を紹介します。

実は、条件を満たす解は条件を満たさない解より圧倒的に多いです。したがって、条件を満たすまで \(1\) から \(N^2\) までの整数を適当に並べる操作を繰り返すことで非常に高い確率でこの問題に正答することができます。

実装例(Python3)

import random
n = int(input())
while True:
    c = [i + 1 for i in range(n * n)]
    random.shuffle(c)
    a = [[c[i * n + j] for j in range(n)] for i in range(n)]
    s = set([sum(a[i][j] for i in range(n)) for j in range(n)]) | set([sum(a[i][j] for j in range(n)) for i in range(n)])
    if len(s) != 2 * n:
        continue
    for b in a:
        print(*b)
    break