C++でグリッド内の魔方陣を数える方法：アルゴリズムと実装を徹底解説

数値の行列が与えられたとき、その中に含まれる魔方陣（マジックスクエア）の個数を見つけるのが本記事の目的です。

魔方陣とは、行列として見た場合に、1から9までの数字がちょうど1回ずつ現れる3×3の行列のことです。数独のグリッドに似た構造を持っています。魔方陣の主な性質は以下のとおりです。

• すべての数字がちょうど1回ずつ出現する。
• 行列内の9つのセルの合計は45になる。
• 各行（3つの数字）の合計は15になる。
• 各列（3つの数字）の合計は15になる。
• 対角線上の3つの数字の合計も15になる。
• これらの合計を満たすためには、5が必ず両対角線の交点（中央）に位置する必要がある。

入力例1

int arr[][] = { { 1,2,3,0 }, { 4,5,6,1 }, { 7,8,9,0 } };

出力

Magic Squares present: 0

説明 − 理解しやすいように行列形式で表すと、次のようになります。

すべての要素は1〜9の範囲内にありますが、行ごとの合計を確認すると、

1+2+3=6 ≠ 4+5+6=15 ≠ 7+8+9=23

となり、行の合計が一致していません。さらに、対角線の合計も15になっていません。したがって、この行列には魔方陣は1つも含まれていないことがわかります。

入力例2

arr[][] = { { 4,3,8,4 }, { 9,5,1,9 }, { 2,7,6,2 } };

出力

Magic Squares present: 1

説明 − 行列形式で確認してみましょう。

左側の3×3部分グリッドに注目すると、すべての数字が一意で、範囲も1〜9に収まっています。

行の合計：4+3+8＝9+5+1＝2+7+6＝15

列の合計：4+9+2＝3+5+7＝8+1+6＝15

対角線の合計：4+5+6＝8+5+2＝15

また、1から9までの合計は45になり、5が両対角線の中央に配置されています。以上の条件をすべて満たすため、このグリッドには魔方陣が1つ存在します。

プログラムで使用するアプローチ

• 整数型配列 Grid[][] に数値を格納し、row と col にそれぞれ行数・列数を保持します。

• 関数 magicSquare(int a, int b … int i) は9つの要素すべてを引数として受け取り、それらが魔方陣を構成するかどうかを判定します。魔方陣であれば1を返し、そうでなければ0を返します。

• 内部では配列 arr[9] を使ってすべての引数を記録し、各セルの出現回数を数えることで一意性を確認します。あるセルのカウントが1未満ならその数値は1〜9の範囲外であり、1より大きければ重複しているため、flag=0 と設定します。

• flag が1のままの場合、行・列・対角線の合計がすべて15であることを検証します。条件を満たせば魔方陣なので1を返し、そうでなければ0を返します。

• 関数 countSquares(int G[3][4], int R, int C) はグリッドとその行数・列数を受け取り、含まれる魔方陣の個数を数えます。

• 変数 count は、見つかった魔方陣の個数を格納するために使用します。

• 先頭の要素から開始し、row-2、col-2 まで走査を行います（3×3行列を切り出すため）。

• 対角線の中央にあたる G[i+1][j+1] が5でない場合、魔方陣は成立しないため、現在の反復をスキップします。この判定により無駄な計算を大幅に削減できます。

• それ以外の場合は、9つの要素すべてを magicSquare() に渡して厳密な判定を行います。

• G[i][j] を含む9つの要素は、G[i][j]、G[i][j+1]、G[i][j+2]、G[i+1][j]、G[i+1][j+1]、G[i+1][j+2]、G[i+2][j]、G[i+2][j+1]、G[i+2][j+2] の組み合わせです。

• 戻り値が1であれば count をインクリメントします。

• 最後に count を結果として返します。

実装例

#include <bits/stdc++.h>
using namespace std;

// 部分グリッドが魔方陣かどうかを確認する
int magicSquare(int a, int b, int c, int d, int e,
                int f, int g, int h, int i){
    int flag = 1; // すべての数字が一意で1〜9の範囲内であることを示すフラグ
    int arr[9] = {0};
    arr[a-1]++;
    arr[b-1]++;
    arr[c-1]++;
    arr[d-1]++;
    arr[e-1]++;
    arr[f-1]++;
    arr[g-1]++;
    arr[h-1]++;
    arr[i-1]++;
    for(int k = 0; k < 9; k++)
        if(arr[k] > 1 || arr[k] < 1){ // 各数字がちょうど1回出現することを確認
            flag = 0;
            break;
        }
    // すべての行・列・対角線の合計が15であることを確認
    if (flag == 1 && (a + b + c) == 15 && (d + e + f) == 15 && (g + h + i) == 15
        && (a + d + g) == 15 && (b + e + h) == 15 && (c + f + i) == 15
        && (a + e + i) == 15 && (c + e + g) == 15)
        return 1;
    return 0;
}

int countSquares(int G[3][4], int R, int C){
    int count = 0;
    for (int i = 0; i < R - 2; i++)
        for (int j = 0; j < C - 2; j++) {
            // 対角線の中央が5でなければ魔方陣は不可能
            if (G[i + 1][j + 1] != 5)
                continue;
            int ismagic = magicSquare(G[i][j], G[i][j + 1], G[i][j + 2],
                                      G[i + 1][j], G[i + 1][j + 1],
                                      G[i + 1][j + 2], G[i + 2][j],
                                      G[i + 2][j + 1], G[i + 2][j + 2]);
            // 魔方陣となる部分グリッドかどうかを確認
            if (ismagic == 1)
                count++;
        }
    return count;
}

int main(){
    int Grid[3][4] = { { 4, 3, 8, 4 }, { 9, 5, 1, 9 }, { 2, 7, 6, 2 } };
    int row = 3;
    int col = 4;
    cout << "Count of Magic Squares in Grid: " << countSquares(Grid, row, col);
    return 0;
}

出力

Count of Magic Squares in Grid: 1