C++で行列が魔方陣（マジックスクエア）かどうかを判定する方法

本記事では、与えられた正方行列が魔方陣（マジックスクエア）であるかどうかをC++で判定する方法を解説します。

魔方陣とは？

魔方陣とは、各行・各列、そして両対角線上の要素の合計値がすべて等しくなるような正方行列のことです。この共通の合計値は「魔定数」と呼ばれることもあります。

例として、次のような3×3の行列を考えてみましょう。

この行列を確認すると、以下のすべての合計が 15 で一致していることがわかります。

• 1行目：6 + 1 + 8 = 15
• 2行目：7 + 5 + 3 = 15
• 3行目：2 + 9 + 4 = 15
• 1列目：6 + 7 + 2 = 15
• 2列目：1 + 5 + 9 = 15
• 3列目：8 + 3 + 4 = 15
• 主対角線：6 + 5 + 4 = 15
• 副対角線：8 + 5 + 2 = 15

したがって、この行列は魔方陣です。

判定アルゴリズムの考え方

行列が魔方陣かどうかを判定する手順は以下の通りです。

1. 主対角線（左上から右下）の合計を求める。
2. 副対角線（右上から左下）の合計を求める。
3. 両者の合計が一致しない場合は、その時点で魔方陣ではないと判定する。
4. 次に、すべての行の合計を計算し、対角線の合計と比較する。一致しない行があれば false を返す。
5. 同様に、すべての列の合計を計算して比較する。
6. すべてのチェックを通過すれば、その行列は魔方陣である。

C++による実装例

#include <iostream>
#define N 3
using namespace std;

bool isMagicSquare(int mat[][N]) {
    int sum_diag = 0, sum_diag_second = 0;

    // 主対角線の合計を計算
    for (int i = 0; i < N; i++)
        sum_diag += mat[i][i];

    // 副対角線の合計を計算
    for (int i = 0; i < N; i++)
        sum_diag_second += mat[i][N - 1 - i];

    // 対角線同士の合計が異なれば魔方陣ではない
    if (sum_diag != sum_diag_second)
        return false;

    // 各行の合計をチェック
    for (int i = 0; i < N; i++) {
        int rowSum = 0;
        for (int j = 0; j < N; j++)
            rowSum += mat[i][j];
        if (rowSum != sum_diag)
            return false;
    }

    // 各列の合計をチェック
    for (int i = 0; i < N; i++) {
        int colSum = 0;
        for (int j = 0; j < N; j++)
            colSum += mat[j][i];
        if (sum_diag != colSum)
            return false;
    }

    return true;
}

int main() {
    int mat[][N] = {{ 6, 1, 8 },
                    { 7, 5, 3 },
                    { 2, 9, 4 }};

    if (isMagicSquare(mat))
        cout << "It is Magic Square";
    else
        cout << "It is Not a magic Square";

    return 0;
}

実行結果

It is Magic Square

計算量について

このアルゴリズムでは、対角線・行・列それぞれに対して行列全体を一度ずつ走査するため、時間計算量は O(N²) となります。N×N の行列サイズに比例して処理時間が増加しますが、追加のメモリはほとんど不要で、空間計算量は O(1) と非常に効率的です。

まとめ

魔方陣の判定は、「主対角線と副対角線の合計が一致すること」を基準とし、そこから全行・全列の合計を順番に検証していくシンプルな方法で実装できます。条件が一つでも満たされない場合は即座に false を返すことで、無駄な計算を省きながら効率よく判定できます。