この記事は はじめてのアドベントカレンダー Advent Calendar 2025 17 日目の記事です。
はじめに
この記事では $N \times N$ のサイズの魔方陣を 1 個作成するアルゴリズムを紹介します。
手計算で機械的に作ることができ、魔方陣を習ったばかりの子どもでも $6 \times 6$ のような大きな魔方陣を作ることができると思います。
アルゴリズムの正当性については完全な証明はしませんが、具体例を見ながらなるべく一般化した記述で確認をします。
また、記事の最後には C++ での実装例も掲載しています。
あまり難しい話にならないようにしたつもりですので、気楽に読んでみてください。
用語解説
$N$ 行 $N$ 列 の正方形に数を書き並べたものを 方陣 と呼びます。
特に $1$ 以上 $N^2$ 以下の整数が重複なく書かれていて、各行・各列・各対角線上にある $N$ 個の整数の和がすべて等しい方陣を 魔方陣 と呼びます。
また、各行・各列・各対角線上にある $N$ 個の整数の和がすべて等しいことを 定和を持つ と言い、その和のことを 定和 と呼びます。
$3 \times 3$ の魔方陣の一例を示します。
\begin{matrix}
2 & 7 & 6 \\
9 & 5 & 1 \\
4 & 3 & 8
\end{matrix}
この例では 1 から 9 までの整数が重複なく登場していて、定和が 15 であることも確認できます。
これらの他にも用語が出てきますが、必要に応じて説明していきます。
補助方陣というアイデア
これ以降、方陣と行列（正方行列）を同一視することがあります。
突然ですが、次の 2 つの行列 $A,B$ を考えます。
A=
\begin{pmatrix}
0 & 2 & 1 \\
2 & 1 & 0 \\
1 & 0 & 2
\end{pmatrix}
,B=
\begin{pmatrix}
1 & 0 & 2 \\
2 & 1 & 0 \\
0 & 2 & 1
\end{pmatrix}
ここで $3A+B$ を計算してみると...
3A+B=
\begin{pmatrix}
3*0+1 & 3*2+0 & 3*1+2 \\
3*2+2 & 3*1+1 & 3*0+0 \\
3*1+0 & 3*0+2 & 3*2+1
\end{pmatrix}
=
\begin{pmatrix}
1 & 6 & 5 \\
8 & 4 & 0 \\
3 & 2 & 7
\end{pmatrix}
実は $3A+B$ は、冒頭で例として出した $3 \times 3$ の魔方陣のそれぞれの数から 1 を引いたものになっています。
見方を変えると、魔方陣のそれぞれの数から 1 を引いたものに関して 3 で割った商を並べた ものが $A$ で、3 で割ったあまりを並べた ものが $B$ になっています。
（さらに別の見方をすれば、3 進法で表した数を特定の桁だけ取り出して並べたものが $A$ や $B$ であるとも言えます。）
このように、
商を表す方陣 $A$ と あまりを表す方陣 $B$ を組み合わせることで魔方陣を作る
というのがこの記事で紹介するアルゴリズムの基本となる考え方です。
なお $A$ や $B$ を 補助方陣 と呼びます。
先ほどの例ではあらかじめ補助方陣が与えられていましたが、実際には補助方陣を自分で作る必要があります。
逆に補助方陣さえ適切に作ることができたならば、魔方陣も作ることができるのです。
この後で紹介するアルゴリズムは結局のところ、補助方陣を作るためのアルゴリズムなのだと覚えておいてください。
補助方陣が満たすべき条件
$N \times N$ の魔方陣を作るために $N \times N$ の補助方陣 $A,B$ を構成することを考えます。
このとき、補助方陣は $N \times N$ の方陣ならなんでもいいというわけではありません。
不適切な補助方陣の例として、次の $A,B$ を考えてみましょう。
A=
\begin{pmatrix}
0 & 1 & 1 \\
2 & 2 & 0 \\
1 & 0 & 2
\end{pmatrix}
,B=
\begin{pmatrix}
1 & 0 & 2 \\
2 & 1 & 2 \\
0 & 1 & 0
\end{pmatrix}
このとき $3A+B$ を計算すると次のようになります。
3A+B=
\begin{pmatrix}
3*0+1 & 3*1+0 & 3*1+2 \\
3*2+2 & 3*2+1 & 3*0+2 \\
3*1+0 & 3*0+1 & 3*2+0
\end{pmatrix}
=
\begin{pmatrix}
1 & 3 & 5 \\
8 & 7 & 2 \\
0 & 1 & 6
\end{pmatrix}
それぞれの数に 1 を足すと最終的に次の方陣ができあがります。
\begin{matrix}
2 & 4 & 6 \\
9 & 8 & 3 \\
1 & 2 & 7
\end{matrix}
これは $2$ が 2 個含まれていますし、定和を持たないので魔方陣ではありません。
このように、補助方陣によっては魔方陣が作れないこともあります。
それでは、魔方陣を作るためにはどのように補助方陣を構成すれば良いのでしょうか？
具体的なアルゴリズムを説明する前に、補助方陣が満たすべき条件について考えてみましょう。
そもそも魔方陣とは次の条件を満たす方陣のことでした。
- $1$ から $N^2$ までの整数を 1 個ずつ含む
- 定和を持つ
それぞれの条件について、補助方陣がどうなっていれば良いのか整理していきます。
補助方陣の条件 1
魔方陣が満たすべき 1 つ目の条件の「$1$ から $N^2$ までの整数を 1 個ずつ含む」について考えます。
補助方陣 $A,B$ は魔方陣に並べる数（から 1 を引いたもの）を $k$ で割った商とあまりに対応しているものとします。
魔方陣には $1$ から $N^2$ までの整数を並べたいので、$A$ は $0$ 以上 $N^2-1$ 以下の整数を $k$ で割ったときの商を並べたものであり、$B$ は $0$ 以上 $N^2-1$ 以下の整数を $k$ で割ったときのあまりを並べたものになります。
ところで、この後に説明するアルゴリズムでは $k$ は必ず $N^2$ の約数になっています。（つまり $N^2$ を割り切れるような $k$ を選んでいます。）
実は、$k$ が $N^2$ の約数であるとき、$0$ 以上 $N^2-1$ 以下の整数すべてを $k$ で割っていくと、商には $0$ 以上 $\frac{N^2}{k}-1$ 以下の整数がちょうど $k$ 回ずつ現れ、あまりには $0$ 以上 $k-1$ 以下の整数がちょうど $\frac{N^2}{k}$ 回ずつ現れます。
具体例で確認してみましょう（クリックで展開／折りたたみ）
$N=6,\ k=4$ とします。
$0,1,2,\dots,35$ を $4$ で割った商を並べると次のようになります。
0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,\dots,7,7,7,7,8,8,8,8
途中を省略していますが、$0$ から $8$ まで順に $4$ 個ずつ連続して並んでいます。
よって、$0$ 以上 $8$ 以下の整数がちょうど $4$ 回ずつ現れることが確認できました。
また、あまりを並べたものは次のようになります。
0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,\dots,0,1,2,3,0,1,2,3
また途中を省略していますが、$0,1,2,3$ という並びが全部で $9$ 回繰り返されています。
よって、$0$ 以上 $3$ 以下の整数がちょうど $9$ 回ずつ現れることが確認できました。
以上のことから、補助方陣 $A,B$ に含まれる数の個数についての条件が得られます。
補助方陣の条件 1
- $A$ は $0$ 以上 $\frac{N^2}{k}-1$ 以下の整数を $k$ 個ずつ含む
- $B$ は $0$ 以上 $k-1$ 以下の整数を $\frac{N^2}{k}$ 個ずつ含む
補助方陣の条件 2
前に示した不適切な補助方陣の例をもう一度見てみましょう。
A=
\begin{pmatrix}
0 & 1 & 1 \\
2 & 2 & 0 \\
1 & 0 & 2
\end{pmatrix}
, \ B=
\begin{pmatrix}
1 & 0 & 2 \\
2 & 1 & 2 \\
0 & 1 & 0
\end{pmatrix}
, \ 3A+B=
\begin{pmatrix}
1 & 3 & 5 \\
8 & 7 & 2 \\
0 & 1 & 6
\end{pmatrix}
$A,B$ には $0,1,2$ が 3 個ずつ含まれていて補助方陣の条件 1 を満たしますが、$3A+B$ には $1$ が 2 個含まれてしまっています。
これはなぜかというと、魔方陣の条件の 1 個目「$1$ から $N^2$ までの整数を 1 個ずつ含む」の中の「1 個ずつ」という部分が、補助方陣の条件 1 だけでは考慮できていないからです。
「1 個ずつ」を満たすため、補助方陣に必要な条件とは何でしょうか？
上の例において、$3A+B$ の中で $1$ が現れているのは第 1 行第 1 列と第 3 行第 2 列です。
$A$ の第 1 行第 1 列と第 3 行第 2 列はどちらも $0$ で等しいです。
$B$ の第 1 行第 1 列と第 3 行第 2 列はどちらも $1$ で等しいです。
つまり、第 1 行第 1 列と第 3 行第 2 列に並べている数字に関して、3 で割った商もあまりも等しいので、3 で割る前の数も等しくなってしまっているのです。
逆に、商かあまりの少なくとも一方が異なっていれば、割る前の数も異なります。
よって、補助方陣 $A,B$ は次の条件を満たす必要があります。
- $N \times N$ マスの中から異なる 2 マスをどのように選んでも、$A$ の対応する 2 マスに書かれた数が異なっているか、$B$ の対応する 2 マスに書かれた数が異なっている
もう少し厳密に書くと次のようになります。
- $i_1,j_1,i_2,j_2$ は $(i_1,j_1) \ne (i_2,j_2)$ を満たす $1$ 以上 $N$ 以下の任意の整数とする。このとき、$A_{i_1,j_1} \ne A_{i_2,j_2}$ と $B_{i_1,j_1} \ne B_{i_2,j_2}$ の少なくとも一方が成り立つ
補助方陣 $A,B$ が上記の条件を満たしていることを、$A$ と $B$ は 互いに直交する と言います。（直交行列という概念もありますがそれとは異なります。）
補助方陣の条件 2
- $A,B$ は互いに直交する
補助方陣の条件 3
魔方陣が満たす条件の 2 個目は「定和を持つ」でした。
これを満たすためには補助方陣 $A,B$ はどうなっていれば良いでしょうか？
魔方陣が定和を持つという条件を、補助方陣が満たす条件に「言い換え」をするのは難しいです。
すなわち、「補助方陣 $A,B$ がある条件を満たすときはできあがる方陣が定和を持ち、$A,B$ がある条件を満たさないときはできあがる方陣が定和を持たない」というような条件（必要十分条件）を考えるのは難しいです。
ですが、「$A,B$ がある条件を満たすときはできあがる方陣が定和を持つ」だけであれば、そのような条件（十分条件）は簡単に作れます。
その条件とはずばり、
- $A,B$ はいずれも定和を持つ
です。$A$ の定和と $B$ の定和は異なっていても構いません。
$A,B$ が定和を持たないときは、できあがる方陣は定和を持つかもしれませんし、持たないかもしれません。
しかし $A,B$ が定和を持つときは、できあがる方陣も必ず定和を持ちます。
我々の目標は魔方陣を 1 個作ることなので、確実に魔方陣を作れるパターンだけを考えればいいのです。
さて、「$A,B$ が定和を持つときはできあがる方陣も定和を持つ」というのは本当なのか確かめてみましょう。
魔方陣の作り方をおさらいしておきます。
$0$ から $N^2-1$ までの整数を $k$ で割った商が補助方陣 $A$、あまりが補助方陣 $B$ に対応しているのでした。
そして、$kA+B$ を計算してからそれぞれの数に 1 を足せば魔方陣になるのでした。
$N=3$ の場合を考えてみましょう。
A=
\begin{pmatrix}
A_{1,1} & A_{1,2} & A_{1,3} \\
A_{2,1} & A_{2,2} & A_{2,3} \\
A_{3,1} & A_{3,2} & A_{3,3}
\end{pmatrix}
, \ B=
\begin{pmatrix}
B_{1,1} & B_{1,2} & B_{1,3} \\
B_{2,1} & B_{2,2} & B_{2,3} \\
B_{3,1} & B_{3,2} & B_{3,3}
\end{pmatrix}
$A$ の定和を $c_A$、$B$ の定和を $c_B$ とします。
このとき、定和の定義から次の等式が成立します。
\begin{align*}
c_A &= A_{1,1} + A_{1,2} + A_{1,3} = A_{2,1} + A_{2,2} + A_{2,3} = A_{3,1} + A_{3,2} + A_{3,3} \\
&= A_{1,1} + A_{2,1} + A_{3,1} = A_{1,2} + A_{2,2} + A_{3,2} = A_{1,3} + A_{2,3} + A_{3,3} \\
&= A_{1,1} + A_{2,2} + A_{3,3} = A_{1,3} + A_{2,2} + A_{3,1} \\
c_B &= B_{1,1} + B_{1,2} + B_{1,3} = B_{2,1} + B_{2,2} + B_{2,3} = B_{3,1} + B_{3,2} + B_{3,3} \\
&= B_{1,1} + B_{2,1} + B_{3,1} = B_{1,2} + B_{2,2} + B_{3,2} = B_{1,3} + B_{2,3} + B_{3,3} \\
&= B_{1,1} + B_{2,2} + B_{3,3} = B_{1,3} + B_{2,2} + B_{3,1}
\end{align*}
このとき $kA+B$ のそれぞれの数に 1 を足した結果は次のようになります。
\begin{pmatrix}
kA_{1,1} + B_{1,1} + 1 & kA_{1,2} + B_{1,2} + 1 & kA_{1,3} + B_{1,3} + 1 \\
kA_{2,1} + B_{2,1} + 1 & kA_{2,2} + B_{2,2} + 1 & kA_{2,3} + B_{2,3} + 1 \\
kA_{3,1} + B_{3,1} + 1 & kA_{3,2} + B_{3,2} + 1 & kA_{3,3} + B_{3,3} + 1
\end{pmatrix}
この行列の第 1 行の要素の和は次のように計算できます。
\begin{align*}
\left( kA_{1,1} + B_{1,1} + 1 \right) + \left( kA_{1,2} + B_{1,2} + 1 \right) + \left( kA_{1,3} + B_{1,3} + 1 \right)
&= \left( kA_{1,1} + kA_{1,2} + kA_{1,3} \right) + \left( B_{1,1} + B_{1,2} + B_{1,3} \right) + 3 \\
&= k \left( A_{1,1} + A_{1,2} + A_{1,3} \right) + \left( B_{1,1} + B_{1,2} + B_{1,3} \right) + 3 \\
&= kc_A + c_B + 3
\end{align*}
他の行・列・対角線の要素の和も同様に計算でき、すべて $kc_A + c_B + 3$ になることが確認できます。
よって、計算結果の方陣は確かに定和を持つことがわかりました。
今回は $N=3$ で考えましたが、一般の $N$ についても、できあがる方陣は定和 $kc_A + c_B + N$ を持つことが証明できます。
補助方陣の条件 3
- $A,B$ はいずれも定和を持つ
補助方陣の条件 まとめ
$N \times N$ の魔方陣を補助方陣 $A,B$ から作成したいときに、$A,B$ が満たしているべき条件をまとめます。
なお、$k$ は $N^2$ の約数とします。
- $A$ は $0$ 以上 $\frac{N^2}{k}-1$ 以下の整数を $k$ 個ずつ含み、$B$ は $0$ 以上 $k-1$ 以下の整数を $\frac{N^2}{k}$ 個ずつ含む
- $A,B$ は互いに直交する
- $A,B$ はいずれも定和を持つ
1 個目と 2 個目の条件を満たしている場合、できあがる方陣は $1$ から $N^2$ までの整数を 1 個ずつ含みます。
3 個目の条件を満たしている場合、できあがる方陣は定和を持ちます。
よって、これらの条件をすべて満たすような補助方陣 $A,B$ を作ることができれば、できあがる方陣は魔方陣になります。
魔方陣を作成するアルゴリズム
いよいよ本題のアルゴリズムを説明していきます。
$N \times N$ の魔方陣を作るアルゴリズムの概要は次の通りです。
- 整数 $k$ および $N \times N$ の補助方陣 $A,B$ を決定する
- $kA+B$ を計算する
- $kA+B$ の各要素に 1 を加える
ここまでは何度か説明してきたので理解できると思います。
重要なのは $k,A,B$ の選び方ですが、$N$ の値に応じて 3 パターンに分かれます。
N が奇数のとき
$N$ が奇数の場合は、$k=N$ とします。
次に補助方陣 $A$ の作り方を説明します。参考のため $N=5$ の場合の例も示します。
最初に 1 行目の中央に $0$ を置きます。
置いた $0$ から右に向かって、数を 1 ずつ増やしながら連続して置いていきます。
このとき左右の端はループしていると考えて 1 行目がすべて埋まるまで続けます。
\begin{matrix}
3 & 4 & 0 & 1 & 2 \\
. & . & . & . & . \\
. & . & . & . & . \\
. & . & . & . & . \\
. & . & . & . & .
\end{matrix}
2 行目は 1 行目の数を左に 1 マスずらして入れます。左右の端はループさせます。
\begin{matrix}
3 & 4 & 0 & 1 & 2 \\
4 & 0 & 1 & 2 & 3 \\
. & . & . & . & . \\
. & . & . & . & . \\
. & . & . & . & .
\end{matrix}
3 行目以降も同様にして 1 つ上の行を左に 1 マスずらして入れます。
\begin{matrix}
3 & 4 & 0 & 1 & 2 \\
4 & 0 & 1 & 2 & 3 \\
0 & 1 & 2 & 3 & 4 \\
1 & 2 & 3 & 4 & 0 \\
2 & 3 & 4 & 0 & 1
\end{matrix}
これで補助方陣 $A$ の完成です。
補助方陣 $B$ は $A$ を左右反転させるだけで作れます。
A=
\begin{pmatrix}
3 & 4 & 0 & 1 & 2 \\
4 & 0 & 1 & 2 & 3 \\
0 & 1 & 2 & 3 & 4 \\
1 & 2 & 3 & 4 & 0 \\
2 & 3 & 4 & 0 & 1
\end{pmatrix}
, \ B=
\begin{pmatrix}
2 & 1 & 0 & 4 & 3 \\
3 & 2 & 1 & 0 & 4 \\
4 & 3 & 2 & 1 & 0 \\
0 & 4 & 3 & 2 & 1 \\
1 & 0 & 4 & 3 & 2
\end{pmatrix}
正当性の確認
上のようにして作った $A,B$ が補助方陣の条件を満たしていることを確認しましょう。
- 条件 1：$A$ は $0$ 以上 $\frac{N^2}{k}-1$ 以下の整数を $k$ 個ずつ含み、$B$ は $0$ 以上 $k-1$ 以下の整数を $\frac{N^2}{k}$ 個ずつ含む
$k=N$ は $N^2$ の約数であることに注意してください。（補助方陣の条件 1 は、$k$ が $N^2$ の約数であることを前提として得られたものです。）
$A$ は 1 行につき $0$ 以上 $N-1$ 以下の整数を 1 個ずつ含み、合計 $N$ 行あるので、全体では $N$ 個ずつとなり条件を満たします。
$B$ は $A$ を反転しただけなので、$0$ 以上 $N-1$ 以下の整数を $N$ 個ずつ含み条件を満たします。
- 条件 2：$A,B$ は互いに直交する
上の例の $A$ の中で $0$ が現れる場所を上から探してみます。
$A$ の第 1 行第 3 列は $0$ で、$B$ の第 1 行第 3 列は $0$ です。
$A$ の第 2 行第 2 列は $0$ で、$B$ の第 2 行第 2 列は $2$ です。
$A$ の第 3 行第 1 列は $0$ で、$B$ の第 3 行第 1 列は $4$ です。
$A$ の第 4 行第 5 列は $0$ で、$B$ の第 4 行第 5 列は $1$ です。
$A$ の第 5 行第 4 列は $0$ で、$B$ の第 5 行第 4 列は $3$ です。
このように同じ商に対応するあまりは 2 ずつ変化していき、同じ商に対して同じあまりが現れることはありません。
したがって条件を満たします。
- 条件 3：$A,B$ はいずれも定和を持つ
$A$ の各行・各列は $0$ 以上 $N-1$ 以下の整数を 1 個ずつ含むので、和は $\frac{N(N-1)}{2}$ です。
$A$ の主対角線（左上と右下を結ぶ対角線）には数が 2 ずつ変化しながら並び、$0$ 以上 $N-1$ 以下の整数が 1 回ずつ現れるので、和は $\frac{N(N-1)}{2}$ です。
$A$ の副対角線（右上と左下を結ぶ対角線）には $\frac{N-1}{2}$ が $N$ 個並ぶため、和は $\frac{N(N-1)}{2}$ です。
よって $A$ は定和 $\frac{N-1}{2}$ を持ちます。
$B$ は $A$ を反転したものなのでやはり定和 $\frac{N-1}{2}$ を持ちます。
以上により $A,B$ は条件 3 を満たします。
N が 4 の倍数のとき
$N$ が 4 の倍数の場合は、$k=N$ とします。
$N=8$ の場合を例に見ながら、補助方陣 $A$ の作り方を説明します。
最初に左上に $0$ を置き、右上に $\frac{N}{2}$ を置きます。
その後、1 行目の中央に向かって数を 1 ずつ増やしながら置いていきます。
このとき中央を跨がないようにします。（$\frac{N}{2}-1$ や $N-1$ を置いたらストップ）
\begin{matrix}
0 & 1 & 2 & 3 & 7 & 6 & 5 & 4 \\
. & . & . & . & . & . & . & . \\
. & . & . & . & . & . & . & . \\
. & . & . & . & . & . & . & . \\
. & . & . & . & . & . & . & . \\
. & . & . & . & . & . & . & . \\
. & . & . & . & . & . & . & . \\
. & . & . & . & . & . & . & .
\end{matrix}
2 行目以降は、1 つ上の行を右に $\frac{N}{2}$ マスずらして入れます。左右の端はループさせます。
\begin{matrix}
0 & 1 & 2 & 3 & 7 & 6 & 5 & 4 \\
7 & 6 & 5 & 4 & 0 & 1 & 2 & 3 \\
0 & 1 & 2 & 3 & 7 & 6 & 5 & 4 \\
7 & 6 & 5 & 4 & 0 & 1 & 2 & 3 \\
0 & 1 & 2 & 3 & 7 & 6 & 5 & 4 \\
7 & 6 & 5 & 4 & 0 & 1 & 2 & 3 \\
0 & 1 & 2 & 3 & 7 & 6 & 5 & 4 \\
7 & 6 & 5 & 4 & 0 & 1 & 2 & 3
\end{matrix}
これで $A$ は完成です。
$B$ は $A$ の行と列を入れ替えると作ることができます。
つまり、$A$ の第 $i$ 行第 $j$ 列にある数を $B$ の第 $j$ 行第 $i$ 列に置けばよく、行列でいうところの転置をします。
A=
\begin{pmatrix}
0 & 1 & 2 & 3 & 7 & 6 & 5 & 4 \\
7 & 6 & 5 & 4 & 0 & 1 & 2 & 3 \\
0 & 1 & 2 & 3 & 7 & 6 & 5 & 4 \\
7 & 6 & 5 & 4 & 0 & 1 & 2 & 3 \\
0 & 1 & 2 & 3 & 7 & 6 & 5 & 4 \\
7 & 6 & 5 & 4 & 0 & 1 & 2 & 3 \\
0 & 1 & 2 & 3 & 7 & 6 & 5 & 4 \\
7 & 6 & 5 & 4 & 0 & 1 & 2 & 3
\end{pmatrix}
, \ B=
\begin{pmatrix}
0 & 7 & 0 & 7 & 0 & 7 & 0 & 7 \\
1 & 6 & 1 & 6 & 1 & 6 & 1 & 6 \\
2 & 5 & 2 & 5 & 2 & 5 & 2 & 5 \\
3 & 4 & 3 & 4 & 3 & 4 & 3 & 4 \\
7 & 0 & 7 & 0 & 7 & 0 & 7 & 0 \\
6 & 1 & 6 & 1 & 6 & 1 & 6 & 1 \\
5 & 2 & 5 & 2 & 5 & 2 & 5 & 2 \\
4 & 3 & 4 & 3 & 4 & 3 & 4 & 3
\end{pmatrix}
正当性の確認
- 条件 1：$A$ は $0$ 以上 $\frac{N^2}{k}-1$ 以下の整数を $k$ 個ずつ含み、$B$ は $0$ 以上 $k-1$ 以下の整数を $\frac{N^2}{k}$ 個ずつ含む
$A$ は 1 行につき $0$ 以上 $N-1$ 以下の整数を 1 個ずつ含み、合計 $N$ 行あるので、全体では $N$ 個ずつとなり条件を満たします。
$B$ は $A$ を転置しただけなので、$0$ 以上 $N-1$ 以下の整数を $N$ 個ずつ含み条件を満たします。
- 条件 2：$A,B$ は互いに直交する
上の例の $A$ の中で $0$ が現れる場所を上から探すと次のようになります。
$A$ の第 1 行第 1 列は $0$ で、$B$ の第 1 行第 1 列は $0$ です。
$A$ の第 2 行第 5 列は $0$ で、$B$ の第 2 行第 5 列は $1$ です。
$A$ の第 3 行第 1 列は $0$ で、$B$ の第 3 行第 1 列は $2$ です。
$A$ の第 4 行第 5 列は $0$ で、$B$ の第 4 行第 5 列は $3$ です。
$A$ の第 5 行第 1 列は $0$ で、$B$ の第 5 行第 1 列は $7$ です。
$A$ の第 6 行第 5 列は $0$ で、$B$ の第 6 行第 5 列は $6$ です。
$A$ の第 7 行第 1 列は $0$ で、$B$ の第 7 行第 1 列は $5$ です。
$A$ の第 8 行第 5 列は $0$ で、$B$ の第 8 行第 5 列は $4$ です。
このように同じ商に対応するあまりの並びは $A$ の第 1 行または第 2 行と一致し、同じあまりは出てきません。
したがって条件を満たします。
- 条件 3：$A,B$ はいずれも定和を持つ
$A$ の各行は $0$ 以上 $N-1$ 以下の整数を 1 個ずつ含むので、和は $\frac{N(N-1)}{2}$ です。
$A$ の各列は、和が $N-1$ になるような 2 数のペアを $\frac{N}{2}$ 組持つので、和は $\frac{N(N-1)}{2}$ です。
$A$ の主対角線上の数を左上から右下へ向かって見ていくと、$A$ の第 1 行の数を $\frac{N}{2}+1$ 個おきに見ていく（左右の端はループさせる）並びと一致し、$0$ 以上 $N-1$ 以下の整数を 1 個ずつ含むため、和は $\frac{N(N-1)}{2}$ です。
$A$ の副対角線上の数を左下から右上へ向かって見ていくと、$A$ の第 $N$ 行の数を $\frac{N}{2}+1$ 個おきに見ていく並びと一致し、$0$ 以上 $N-1$ 以下の整数を 1 個ずつ含むため、和は $\frac{N(N-1)}{2}$ です。
以上より $A$ は定和 $\frac{N(N-1)}{2}$ を持ちます。
$B$ は $A$ の転置なので同じく定和 $\frac{N(N-1)}{2}$ を持ちます。
よって条件 3 は満たされていることがわかります。
N が 4 の倍数でない偶数のとき
この場合は LUX 法 と呼ばれる方法で作ることができます。
正の整数 $m$ を用いて $N=4m+2$ とおきます。
なお、$2 \times 2$ の魔方陣は存在しないため、$m \ge 1$ となります。
LUX 法では $k=4$ とします。
次に補助方陣 $A$ を作ります。$N=10$ の場合を例とします。
まずは、すでに説明した $N$ が奇数の場合の方法を使って $(2m+1) \times (2m+1)$ の魔方陣を作ります。
その後、それぞれの数から 1 を引くことで $0$ 以上 $(2m+1)^2-1$ 以下の整数が含まれるようにします。
\begin{matrix}
17 & 21 & 0 & 9 & 13 \\
23 & 2 & 6 & 10 & 19 \\
4 & 8 & 12 & 16 & 20 \\
5 & 14 & 18 & 22 & 1 \\
11 & 15 & 24 & 3 & 7
\end{matrix}
この $(2m+1) \times (2m+1)$ の方陣を縦横に 2 倍に拡大した $N \times N$ の方陣を $A$ とします。
\begin{matrix}
17 & 17 & 21 & 21 & 0 & 0 & 9 & 9 & 13 & 13 \\
17 & 17 & 21 & 21 & 0 & 0 & 9 & 9 & 13 & 13 \\
23 & 23 & 2 & 2 & 6 & 6 & 10 & 10 & 19 & 19 \\
23 & 23 & 2 & 2 & 6 & 6 & 10 & 10 & 19 & 19 \\
4 & 4 & 8 & 8 & 12 & 12 & 16 & 16 & 20 & 20 \\
4 & 4 & 8 & 8 & 12 & 12 & 16 & 16 & 20 & 20 \\
5 & 5 & 14 & 14 & 18 & 18 & 22 & 22 & 1 & 1 \\
5 & 5 & 14 & 14 & 18 & 18 & 22 & 22 & 1 & 1 \\
11 & 11 & 15 & 15 & 24 & 24 & 3 & 3 & 7 & 7 \\
11 & 11 & 15 & 15 & 24 & 24 & 3 & 3 & 7 & 7
\end{matrix}
次に補助方陣 $B$ を作ります。
まず $(2m+1) \times (2m+1)$ のマス目を考えます。
1 行目から $m+1$ 行目を $L$ で埋め、$m+2$ 行目を $U$ で埋め、$m+3$ 行目以降が存在するなら $X$ で埋めます。
\begin{matrix}
L & L & L & L & L \\
L & L & L & L & L \\
L & L & L & L & L \\
U & U & U & U & U \\
X & X & X & X & X
\end{matrix}
$m+1$ 行目の中央にある $L$ と、すぐ下にある $U$ を入れ替えます。
\begin{matrix}
L & L & L & L & L \\
L & L & L & L & L \\
L & L & U & L & L \\
U & U & L & U & U \\
X & X & X & X & X
\end{matrix}
$L,U,X$ を次のように置き換えると $B$ が得られます。
文字と置き換え先の数との対応は $m$ に依存しません。
L=
\begin{pmatrix}
3 & 0 \\
1 & 2
\end{pmatrix}
, \ U=
\begin{pmatrix}
0 & 3 \\
1 & 2
\end{pmatrix}
, \ X=
\begin{pmatrix}
0 & 3 \\
2 & 1
\end{pmatrix}
\begin{matrix}
3 & 0 & 3 & 0 & 3 & 0 & 3 & 0 & 3 & 0 \\
1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\
3 & 0 & 3 & 0 & 3 & 0 & 3 & 0 & 3 & 0 \\
1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\
3 & 0 & 3 & 0 & 0 & 3 & 3 & 0 & 3 & 0 \\
1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\
0 & 3 & 0 & 3 & 3 & 0 & 0 & 3 & 0 & 3 \\
1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\
0 & 3 & 0 & 3 & 0 & 3 & 0 & 3 & 0 & 3 \\
2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1
\end{matrix}
正当性の確認
- 条件 1：$A$ は $0$ 以上 $\frac{N^2}{k}-1$ 以下の整数を $k$ 個ずつ含み、$B$ は $0$ 以上 $k-1$ 以下の整数を $\frac{N^2}{k}$ 個ずつ含む
$N$ は偶数なので $N^2$ は 4 の倍数です。よって $k=4$ は $N^2$ の約数です。
$A$ が条件を満たすことは $A$ の作り方から明らかです。
$B$ については、文字 $L,U,X$ を合計 $\frac{N^2}{4}$ 文字含んでいて、それぞれの文字には $0$ 以上 $3$ 以下の整数が 1 個ずつ含まれるので、条件を満たします。
- 条件 2：$A,B$ は互いに直交する
$A$ において同じ数が置かれている場所は、$B$ において元々 1 個の文字だった場所に対応します。
$L,U,X$ を置き換えるとき 1 個の文字は異なる 4 個の数に置き換えられるので、$A$ の同じ商に対応する $B$ のあまりはすべて異なります。
よって条件を満たします。
- 条件 3：$A,B$ はいずれも定和を持つ
$A$ は拡大する前の方陣が定和を持つため、拡大後である $A$ も定和を持ちます。
$B$ の各行は和が $3$ になるような 2 数のペアを $\frac{N}{2}$ 組持つので、和は $\frac{3N}{2} = \frac{3(4m+2)}{2} = 6m+3$ です。
$B$ の各列に含まれる文字の個数は、$L$ が $m+1$ 個、$U$ が $1$ 個、$X$ が $m-1$ 個です。
$B$ の奇数列目では、$L$ 1 個から置き換えられる数の和は $3+1=4$、同様に $U$ からは $0+1=1$、$X$ からは $0+2=2$ なので、1 列の合計は $4(m+1) + 1 + 2(m-1) = 6m+3$ です。
$B$ の偶数列目では、$L$ 1 個から置き換えられる数の和は $0+2=2$、同様に $U$ からは $3+2=5$、$X$ からは $3+1=4$ なので、1 列の合計は $2(m+1) + 5 + 4(m-1) = 6m+3$ です。
$B$ の対角線上に含まれる文字の個数は、$L$ が $m$ 個、$U$ が $2$ 個、$X$ が $m-1$ 個です。
主対角線上の数のうち、$L$ 1 個から置き換えられる数の和は $3+2=5$、同様に $U$ からは $0+2=2$、$X$ からは $0+1=1$ なので、主対角線上の数の和は $5m+2 \times 2+(m-1) = 6m+3$ です。
副対角線上の数のうち、$L$ 1 個から置き換えられる数の和は $0+1=1$、同様に $U$ からは $3+1=4$、$X$ からは $3+2=5$ なので、主対角線上の数の和は $m+4 \times 2+5(m-1) = 6m+3$ です。
よって $B$ は定和 $6m+3$ を持ちます。
補助方陣を作った後の計算例
これですべての場合について魔方陣の作り方の説明が終わりました。
念のため $N=5$ の場合について最終的に魔方陣ができるまでの計算例を掲載しておきます。
説明した手順に沿うと $k=5$ となり、補助方陣 $A,B$ は次のようになります。
A=
\begin{pmatrix}
3 & 4 & 0 & 1 & 2 \\
4 & 0 & 1 & 2 & 3 \\
0 & 1 & 2 & 3 & 4 \\
1 & 2 & 3 & 4 & 0 \\
2 & 3 & 4 & 0 & 1
\end{pmatrix}
, \ B=
\begin{pmatrix}
2 & 1 & 0 & 4 & 3 \\
3 & 2 & 1 & 0 & 4 \\
4 & 3 & 2 & 1 & 0 \\
0 & 4 & 3 & 2 & 1 \\
1 & 0 & 4 & 3 & 2
\end{pmatrix}
$5A+B$ を計算します。
5A+B=
\begin{pmatrix}
5 \times 3+2 & 5 \times 4+1 & 5 \times 0+0 & 5 \times 1+4 & 5 \times 2+3 \\
5 \times 4+3 & 5 \times 0+2 & 5 \times 1+1 & 5 \times 2+0 & 5 \times 3+4 \\
5 \times 0+4 & 5 \times 1+3 & 5 \times 2+2 & 5 \times 3+1 & 5 \times 4+0 \\
5 \times 1+0 & 5 \times 2+4 & 5 \times 3+3 & 5 \times 4+2 & 5 \times 0+1 \\
5 \times 2+1 & 5 \times 3+0 & 5 \times 4+4 & 5 \times 0+3 & 5 \times 1+2
\end{pmatrix}
=
\begin{pmatrix}
17 & 21 & 0 & 9 & 13 \\
23 & 2 & 6 & 10 & 19 \\
4 & 8 & 12 & 16 & 20 \\
5 & 14 & 18 & 22 & 1 \\
11 & 15 & 24 & 3 & 7
\end{pmatrix}
すべての数に 1 を足して完成です。
\begin{matrix}
18 & 22 & 1 & 10 & 14 \\
24 & 3 & 7 & 11 & 20 \\
5 & 9 & 13 & 17 & 21 \\
6 & 15 & 19 & 23 & 2 \\
12 & 16 & 25 & 4 & 8
\end{matrix}
おわりに
魔方陣の作り方はいくつも考案されてきました。
今回紹介した方法では 1 通りの魔方陣しか作れませんが、同じサイズでも様々な魔方陣を作れるような方法も存在しています。
参考文献を載せていますので興味がある方は調べてみてはいかがでしょうか。
この記事は年末の気分転換になるような内容を目指して執筆してみましたが、これを読んだ方がそう思えていれば嬉しいです。
この記事を読んで少しでも楽しんでいただけたら、いいねを押してもらえると筆者が喜びます。よろしくお願いします。
それでは、ここまでお読みいただきありがとうございました。
余談
筆者が魔方陣について調べることとなったきっかけは AtCoder のとある問題の解法の一部として（準）魔方陣を作りたくなったことでした。（リンク先ネタバレ注意）
余裕があれば年末年始にでもユーザー解説を書いてみたいです。
ちなみに、魔方陣について調べるうちに上記の問題にほぼそのまま適用できるアルゴリズムがネットに書かれているのを発見しました。
やっぱりユーザー解説は書かなくてもいいかもしれません。
参考文献
実装例 (C++)
計算量は $O(N^2)$ で、マス目の数に対して線形時間です。
#include <algorithm>
#include <cassert>
#include <print>
#include <ranges>
#include <utility>
#include <vector>
using square = std::vector<std::vector<int>>;
square create_magic_square(int);
std::pair<square, square> create_preliminary_squares_odd(const int n) {
square a, b;
a = square(n, std::vector<int>(n));
for (const int i : std::views::iota(0, n)) {
for (const int j : std::views::iota(0, n)) {
a[i][j] = (i + j + (n + 1) / 2) % n;
}
}
b = a | std::views::transform([](const auto& row) {
return row | std::views::reverse;
}) |
std::ranges::to<square>();
return {a, b};
}
std::pair<square, square> create_preliminary_squares_doubly_even(const int n) {
square a, b;
const auto former = std::views::iota(0, n / 2);
const auto latter = std::views::iota(n / 2, n) | std::views::reverse;
// 本当は std::views::concat を使いたいが筆者の環境では不可
std::vector<int> first_two_rows(0);
first_two_rows.append_range(former);
first_two_rows.append_range(latter);
first_two_rows.append_range(latter);
first_two_rows.append_range(former);
a = std::views::repeat(first_two_rows, n / 2) | std::views::join |
std::views::chunk(n) | std::ranges::to<square>();
b = square(n, std::vector<int>(n));
for (const int i : std::views::iota(0, n)) {
for (const int j : std::views::iota(0, n)) {
b[i][j] = a[j][i];
}
}
return {a, b};
}
std::pair<square, square> create_preliminary_squares_singly_even(const int n) {
square a, b;
a = square(n, std::vector<int>(n));
const square half = create_magic_square(n / 2);
for (const int i : std::views::iota(0, n)) {
for (const int j : std::views::iota(0, n)) {
a[i][j] = half[i / 2][j / 2] - 1;
}
}
b = square(n, std::vector<int>(n));
const square L = {{3, 0}, {1, 2}}, U = {{0, 3}, {1, 2}},
X = {{0, 3}, {2, 1}};
for (const int i : std::views::iota(0, n)) {
for (const int j : std::views::iota(0, n)) {
if (i / 2 > (n - 2) / 4 + 1) {
b[i][j] = X[i % 2][j % 2];
} else if (i / 2 < (n - 2) / 4) {
b[i][j] = L[i % 2][j % 2];
} else if ((i / 2 == (n - 2) / 4) ^ (j / 2 == (n - 2) / 4)) {
b[i][j] = L[i % 2][j % 2];
} else {
b[i][j] = U[i % 2][j % 2];
}
}
}
return {a, b};
}
square create_magic_square(const int n) {
if (n <= 0 || n == 2) return square();
int k;
square a, b;
if (n % 2 == 1) {
k = n;
std::tie(a, b) = create_preliminary_squares_odd(n);
} else if (n % 4 == 0) {
k = n;
std::tie(a, b) = create_preliminary_squares_doubly_even(n);
} else {
k = 4;
std::tie(a, b) = create_preliminary_squares_singly_even(n);
}
return std::views::zip_transform(
[&](const int q, const int r) { return k * q + r + 1; },
a | std::views::join, b | std::views::join) |
std::views::chunk(n) | std::ranges::to<square>();
}
void check(const square sq) {
const int n = int(sq.size());
for (const auto& row : sq) assert(int(row.size()) == n);
std::vector<bool> seen_value(n * n, false);
for (const auto& row : sq) {
for (const int value : row) {
seen_value[value - 1] = true;
}
}
assert(
std::ranges::all_of(seen_value, [](const auto& seen) { return seen; }));
const int c = n * (n * n + 1) / 2;
for (const auto& row : sq) {
assert(std::ranges::fold_left(row, 0, std::plus<>()) == c);
}
for (const int j : std::views::iota(0, n)) {
assert(
std::ranges::fold_left(std::views::iota(0, n) |
std::views::transform([&](const int i) {
return sq[i][j];
}),
0, std::plus<>()) == c);
}
assert(std::ranges::fold_left(
std::views::iota(0, n) |
std::views::transform([&](const int i) { return sq[i][i]; }),
0, std::plus<>()) == c);
assert(std::ranges::fold_left(
std::views::iota(0, n) | std::views::transform([&](const int i) {
return sq[i][n - 1 - i];
}),
0, std::plus<>()) == c);
}
int main() {
const square magic4 = create_magic_square(4);
for (const auto& row : magic4) std::println("{}", row);
const square magic5 = create_magic_square(5);
for (const auto& row : magic5) std::println("{}", row);
const square magic6 = create_magic_square(6);
for (const auto& row : magic6) std::println("{}", row);
for (const int n : std::views::iota(3, 100)) {
const square magic = create_magic_square(n);
check(magic);
}
}
[1, 8, 13, 12]
[14, 11, 2, 7]
[4, 5, 16, 9]
[15, 10, 3, 6]
[18, 22, 1, 10, 14]
[24, 3, 7, 11, 20]
[5, 9, 13, 17, 21]
[6, 15, 19, 23, 2]
[12, 16, 25, 4, 8]
[32, 29, 4, 1, 24, 21]
[30, 31, 2, 3, 22, 23]
[12, 9, 17, 20, 28, 25]
[10, 11, 18, 19, 26, 27]
[13, 16, 36, 33, 5, 8]
[14, 15, 34, 35, 6, 7]