C++ですべての行の合計が等しくなるようにN²個の数値を行列に配置する方法

問題概要

この問題では、整数値 N が与えられます。1 から N² までの数値を、各行の要素の合計がすべて等しくなるように、サイズ N×N の2次元行列（マトリックス）に配置して出力することが課題です。

具体例を見て問題を理解しましょう。

入力： N = 4

出力：

1 6 11 16
2 7 12 13
3 8 9 14
4 5 10 15

この場合、各行の要素の合計はすべて 34 になります。

解決アプローチ

この問題を解くには、各行の合計が等しくなるように各要素を適切な位置に配置する必要があります。ここでは貪欲法（グリーディー法）の考え方を用いて、行ごとに正しい要素を配置していきます。

まず、1 から N² までの数値を順番に初期行列（prevMat）に格納します。次に、以下の変換式を使って新しい行列（resultMat）を作成します。

resultMat[i][j] = prevMat[j][(i+j)%n]

この式により、元の行列の列方向の要素を循環的にシフトしながら再配置することで、すべての行の合計が等しい行列を生成できます。1〜N² の総和は必ず N の倍数になるため、この手法は常に成立します。

C++での実装例

#include<iostream>
using namespace std;

int main(){
    int n = 4, i, j;
    cout << "Matrix of size : " << n << " in which sum of elements of all rows is equal is :\n";

    int prevMat[n][n], resultMat[n][n];
    int c = 1;

    // 初期行列に1からN^2までの数値を格納
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            prevMat[i][j] = c++;
    }

    // 変換式を用いて新しい行列を作成
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            resultMat[i][j] = prevMat[j][(i+j) % n];
        }
    }

    // 結果の出力
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            cout << resultMat[i][j] << "\t";
        }
        cout << endl;
    }
}

出力結果

Matrix of size : 4 in which sum of elements of all rows is equal is :
1 6 11 16
2 7 12 13
3 8 9 14
4 5 10 15

まとめ

変換式 resultMat[i][j] = prevMat[j][(i+j)%n] を使うことで、時間計算量 O(N²) で、すべての行の合計が等しくなる N×N 行列を効率的に生成できます。各行の合計は理論上 N(N²+1)/2 となり、上記の例では 4 × 17 ÷ 2 = 34 となり、実際の出力と一致します。