No.217 魔方陣を作ろう

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 55
作問者 : tailstails
3 ProblemId : 557 / 出題時の順位表

問題文

$N$ 行 $N$ 列の魔方陣を1つ作ってください。
一般に $N$ 行 $N$ 列の魔方陣は複数存在しますが、どれでも構いません。

この問題において、 $N$ 行 $N$ 列の魔方陣とは、
$1$ から $N^2$ までの整数を $N$ 行 $N$ 列に並べたものであって、
各行、各列、及び2つの対角線それぞれについて、そこに並んだ数の総和がいずれも等しくなるもののことをいいます。

$3$ 行 $3$ 列の魔方陣の一例:

2 9 4
7 5 3
6 1 8

競技プログラミングではあまり出てこないアルゴリズムのため、ヒントとしてWikipedia『魔方陣』の「魔方陣の作り方」を参照してもよい。
答えを求めるためにはいくつかのアルゴリズムを組み合わせる必要がある。

入力

$N$

$3 \le N \le 20$
$N$ は整数です。

出力

$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,N}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,N}$

$N$ 行 $N$ 列の魔方陣を1つ出力してください。
出力の $y$ 行目に、魔方陣の $y$ 行目の数を、 $1$ 列目の数 $A_{y,1}$ から順に空白区切りで出力してください。
(数の前後に余分な空白があっても構いません。)

サンプル

サンプル1
入力
3
出力
2 9 4
7 5 3
6 1 8

上記の出力は例です。
$3$ 行 $3$ 列の魔方陣は複数存在しますが、どれを出力しても構いません。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。