C++でグリッド内の魔方陣（3×3マジックスクエア）を数える方法

グリッド内の魔方陣とは

与えられたグリッドの中に、「魔方陣（マジックスクエア）」の条件を満たす3×3の部分グリッドがいくつ含まれているかを求める問題を考えてみましょう。ここでいう魔方陣とは、1から9までの相異なる数字で埋められた3×3の格子であり、各行・各列・そして両対角線の合計がすべて等しいものを指します。

たとえば、次のような入力が与えられたとします。

この場合の出力は 1 になります。左上にある次の3×3の部分グリッドが魔方陣を形成しているためです。

実際に確かめてみると、どの行も列も対角線も合計が15になっており、魔方陣の条件を満たしていることがわかります。

解き方の考え方

この問題を効率的に解く鍵となるのは、1〜9の数字をすべて使う3×3の魔方陣は、回転・反転を含めても全部で8通りしか存在しないという事実です（このとき中心のマスは必ず5になります）。そこで、正しい魔方陣のパターンをあらかじめすべて列挙して集合として持っておけば、グリッド上の各3×3領域をその集合と照合するだけで答えが求まります。

判定のしかたはシンプルです。各セルの値は必ず1桁（1〜9）なので、3×3領域の9つの数字を左上から順に連結すれば、その領域を一意な9桁の整数として表現できます。この値が事前計算した集合に含まれるかどうかを調べるだけでよいのです。具体的な手順は以下のとおりです。

• 正しい魔方陣を9桁の整数に符号化した値の集合 s を定義する：{816357492, 834159672, 618753294, 672159834, 492357816, 438951276, 294753618, 276951438}
• 注目セルから見た3×3領域内の相対位置（オフセット）を格納した、サイズ9×2の配列 offset を用意する：{{-2,-2},{-2,-1},{-2,0},{-1,-2},{-1,-1},{-1,0},{0,-2},{0,-1},{0,0}}
• ans := 0 で初期化する
• i を 2 からグリッドの行数未満まで1ずつ増やしながら、さらに j を 2 からグリッドの列数未満まで1ずつ増やしながら以下を繰り返す
  • sum := 0 で初期化する
  • k を 0 から 8 まで1ずつ増やしながら「sum := sum × 10」「sum := sum + grid[i + offset[k][0]][j + offset[k][1]]」を実行し、3×3領域を9桁の整数に変換する
  • sum が集合 s に含まれていれば ans を1増やす
• 最後に ans を返す

各3×3領域の判定はわずか9回の参照で済むため、全体の計算量はグリッドのサイズに対して O(行数 × 列数) と非常に効率的です。

なお、サンプルコードでは簡潔さのため内外両方のループ条件に grid.size() を使用していますが、行数と列数が異なる長方形のグリッドを扱う場合は、内側のループで列数（grid[0].size()）を使うようにしてください。

C++による実装例

それでは、理解を深めるために実際の実装を見てみましょう。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        const unordered_set<int> s{816357492, 834159672, 618753294,
        672159834, 492357816, 438951276, 294753618, 276951438};
        const int offset[][2] = {{-2, -2}, {-2, -1}, {-2, 0},
{-1, -2}, {-1, -1}, {-1, 0},
{ 0, -2}, { 0, -1}, { 0, 0}};
        int ans = 0;
        for(int i = 2; i < grid.size(); i++)
        {
            for(int j = 2; j < grid.size(); j++)
            {
               int sum = 0;
               for(int k = 0; k < 9; k++)
               {
                  sum *= 10;
                  sum += grid[i + offset[k][0]][j + offset[k][1]];
               }
               ans += s.count(sum);
            }
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{4,3,8,4},{9,5,1,9},{2,7,6,2}};
    cout << (ob.numMagicSquaresInside(v));
}

入力

{{4,3,8,4},{9,5,1,9},{2,7,6,2}}

出力

1