[C言語] 魔方陣を生成するアルゴリズムを実装する方法

魔方陣を生成するアルゴリズムは、通常「奇数次魔方陣」を作成するために「シアム法(Siamese method)」がよく使われます。

この方法では、1から順に数値を配置し、各行・列・対角線の和が同じになるようにします。

具体的には、次の手順で実装します。

この記事でわかること

魔方陣の基本と特徴
奇数次魔方陣の生成アルゴリズム
C言語での実装手順
偶数次魔方陣の生成方法
魔方陣の応用例と実用性

目次から探す

魔方陣とは何か

魔方陣とは、正方形のグリッドに数字を配置し、各行、各列、対角線の合計がすべて同じになるようにした配置のことを指します。

この合計値を「魔方陣の和」と呼びます。

魔方陣は、数学やパズル、ゲームなどで広く利用されており、特に整数の配置に関する興味深い性質を持っています。

魔方陣の基本的な特徴

サイズ: 魔方陣は通常、奇数次(3×3, 5×5など)または偶数次(4×4, 6×6など)で構成されます。
魔方陣の和: \( S = \frac{n(n^2 + 1)}{2} \) で計算され、ここで \( n \) は魔方陣の次元です。
配置のルール: 各数字は1から \( n^2 \) までの整数を使用し、重複は許されません。

魔方陣の種類

スクロールできます

種類	説明
奇数次魔方陣	3, 5, 7などのサイズで構成される魔方陣。
偶数次魔方陣	4, 6, 8などのサイズで構成される魔方陣。
パーフェクト魔方陣	各行、列、対角線の和が同じで、さらに特定の条件を満たす魔方陣。

魔方陣は古代から存在し、さまざまな文化や時代で研究されてきました。

特に、数学的な美しさやパズルとしての楽しさから、多くの人々に親しまれています。

奇数次魔方陣の生成アルゴリズム

シアム法(Siamese method)とは

シアム法は、奇数次の魔方陣を生成するための古典的なアルゴリズムです。

この方法は、特定のルールに従って数字を配置することで、魔方陣を効率的に作成します。

シアム法は、特に3×3や5×5の魔方陣を生成する際に広く使用されており、シンプルで理解しやすいのが特徴です。

シアム法の基本ルール

シアム法には以下の基本ルールがあります。

初期位置: 数字1は、最上行の中央に配置します。
移動ルール: 次の数字は、現在の位置から右上に移動します。
範囲外の処理: 右上に移動した結果、範囲外になった場合は、反対側から入ります。
既存の位置: 移動先にすでに数字がある場合は、現在の位置の下に配置します。

シアム法の手順

数字1を最上行の中央に配置する。
次の数字を右上に移動する。
移動先が範囲外の場合は、反対側から入る。
移動先に数字がある場合は、現在の位置の下に配置する。
すべての数字が配置されるまで、手順2から4を繰り返す。

シアム法の例(3×3魔方陣)

3×3の魔方陣をシアム法で生成する手順を示します。

数字1を配置

0 1 0
0 0 0
0 0 0

数字2を右上に移動して配置

0 1 0
0 0 2
0 0 0

数字3を右上に移動(範囲外)して反対側から入る

0 1 0
0 0 2
3 0 0

数字4を右上に移動して配置

0 1 0
4 0 2
3 0 0

数字5を右上に移動(既存の位置)して下に配置

0 1 0
4 0 2
3 5 0

数字6を右上に移動して配置

6 1 0
  4 0 2
  3 5 0

数字7を右上に移動して配置

6 1 7
4 0 2
3 5 0

数字8を右上に移動(既存の位置)して下に配置

6 1 7
4 8 2
3 5 0

数字9を右上に移動して配置

6 1 7
4 8 2
3 5 9

最終的な3×3魔方陣は以下のようになります。

8 1 6
3 5 7
4 9 2

シアム法の利点と制約

利点

シンプルさ: アルゴリズムが簡単で、理解しやすい。
効率性: 手順が明確で、短時間で魔方陣を生成できる。

制約

奇数次専用: 偶数次の魔方陣には適用できない。
特定の配置: 初期位置や移動ルールに従う必要があり、柔軟性がない。

C言語で魔方陣を実装する準備

必要なライブラリと環境設定

C言語で魔方陣を生成するプログラムを実装するためには、基本的な標準ライブラリを使用します。

以下のライブラリをインクルードします。

#include <stdio.h>  // 入出力関数を使用するため
#include <stdlib.h> // 動的メモリ割り当てを使用するため

これにより、コンソールへの出力やメモリ管理が可能になります。

開発環境としては、GCCやClangなどのCコンパイラを使用することをお勧めします。

配列の基本操作

C言語では、配列を使用してデータを格納します。

配列の基本操作には以下のようなものがあります。

配列の宣言: int array[SIZE]; で配列を宣言します。
要素へのアクセス: array[index] で特定の要素にアクセスします。
要素の代入: array[index] = value; で要素に値を代入します。

2次元配列の扱い方

魔方陣は2次元配列で表現されます。

2次元配列の基本操作は以下の通りです。

2次元配列の宣言: int matrix[SIZE][SIZE]; で2次元配列を宣言します。
要素へのアクセス: matrix[row][column] で特定の要素にアクセスします。
要素の代入: matrix[row][column] = value; で要素に値を代入します。

ループと条件分岐の復習

魔方陣を生成する際には、ループと条件分岐が重要な役割を果たします。

以下は基本的な構文です。

forループ: 繰り返し処理を行うために使用します。

for (int i = 0; i < SIZE; i++) {
    // 繰り返し処理
}

whileループ: 条件が真である限り繰り返し処理を行います。

while (condition) {
    // 繰り返し処理
}

if文: 条件に基づいて処理を分岐させます。

if (condition) {
    // 条件が真の場合の処理
} else {
    // 条件が偽の場合の処理
}

これらの基本的な操作を理解することで、魔方陣を生成するプログラムを効率的に実装する準備が整います。

C言語での魔方陣生成アルゴリズムの実装

魔方陣のサイズを決定する

魔方陣のサイズは奇数でなければなりません。

ユーザーからサイズを入力してもらい、適切なサイズであることを確認します。

以下のように、サイズを決定するためのコードを記述します。

int size;
printf("魔方陣のサイズを入力してください(奇数): ");
scanf("%d", &size);
if (size % 2 == 0) {
    printf("サイズは奇数でなければなりません。\n");
    return 1; // エラー終了
}

初期位置の設定

魔方陣の初期位置は、最上行の中央に設定します。

以下のように、初期位置を設定します。

int matrix[size][size]; // 2次元配列の宣言
memset(matrix, 0, sizeof(matrix)); // 配列を0で初期化
int row = 0; // 初期行
int col = size / 2; // 初期列(中央)

右上斜め移動の実装

次の数字を配置するために、現在の位置から右上に移動します。

移動の実装は以下のようになります。

// 右上斜め移動
int newRow = row - 1;
int newCol = col + 1;

row--; // 行を1つ上に移動
col++; // 列を1つ右に移動

範囲外の処理(ラップアラウンド)

移動した結果、範囲外になった場合は、反対側から入る処理を行います。

以下のように実装します。

// 範囲外の処理(ラップアラウンド)
if (newRow < 0) {
    newRow = size - 1; // 上端を越えた場合、下端に移動
}
if (newCol >= size) {
    newCol = 0; // 右端を越えた場合、左端に移動
}

既存の位置に数値がある場合の処理

移動先にすでに数字がある場合は、現在の位置の下に配置します。

以下のように実装します。

// 既存の位置に数値がある場合の処理
if (matrix[newRow][newCol] != 0) { // すでに数字がある場合
    row += 1;                      // 元の位置の下に移動
    // 列はそのまま
} else {
    row = newRow;
    col = newCol;
}

完成した魔方陣の表示方法

魔方陣が完成したら、2次元配列の内容を表示します。

以下のように表示するためのコードを記述します。

// 完成した魔方陣の表示
for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
        printf("%2d ", matrix[i][j]); // 整形して表示
    }
    printf("\n"); // 行の区切り
}

完成したサンプルコード

以下に、上記のすべての要素を組み合わせた完成したサンプルコードを示します。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    int size;
    printf("魔方陣のサイズを入力してください(奇数): ");
    scanf("%d", &size);

    if (size % 2 == 0) {
        printf("サイズは奇数でなければなりません。\n");
        return 1; // エラー終了
    }

    int matrix[size][size];            // 2次元配列の宣言
    memset(matrix, 0, sizeof(matrix)); // 配列を0で初期化

    int row = 0;        // 初期行
    int col = size / 2; // 初期列(中央)

    for (int num = 1; num <= size * size; num++) {
        matrix[row][col] = num; // 数字を配置

        // 右上斜め移動
        int newRow = row - 1;
        int newCol = col + 1;

        // 範囲外の処理(ラップアラウンド)
        if (newRow < 0) {
            newRow = size - 1; // 上端を越えた場合、下端に移動
        }
        if (newCol >= size) {
            newCol = 0; // 右端を越えた場合、左端に移動
        }

        // 既存の位置に数値がある場合の処理
        if (matrix[newRow][newCol] != 0) { // すでに数字がある場合
            row += 1;                      // 元の位置の下に移動
            // 列はそのまま
        } else {
            row = newRow;
            col = newCol;
        }
    }

    // 完成した魔方陣の表示
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            printf("%2d ", matrix[i][j]); // 整形して表示
        }
        printf("\n"); // 行の区切り
    }

    return 0; // 正常終了
}

このコードを実行すると、指定したサイズの奇数次魔方陣が生成され、コンソールに表示されます。

魔方陣生成アルゴリズムの最適化

メモリ効率の向上

魔方陣を生成する際に使用するメモリを効率的に管理することは重要です。

以下の方法でメモリ効率を向上させることができます。

動的メモリ割り当て: 固定サイズの配列を使用する代わりに、mallocを使用して動的にメモリを割り当てることで、必要なサイズだけメモリを使用します。

int **matrix = (int **)malloc(size * sizeof(int *));
for (int i = 0; i < size; i++) {
    matrix[i] = (int *)malloc(size * sizeof(int));
}

メモリの解放: 使用が終わったメモリは必ずfreeを使って解放し、メモリリークを防ぎます。

for (int i = 0; i < size; i++) {
    free(matrix[i]);
}
free(matrix);

計算量の削減

魔方陣生成の計算量を削減するためには、以下の点に注意します。

ループの最適化: 不要な計算を避けるために、ループの条件を見直し、必要な処理だけを行うようにします。
条件分岐の簡素化: 複雑な条件分岐を減らし、処理を効率化します。

例えば、範囲外の処理を一つの関数にまとめることで、コードの可読性と効率を向上させます。

エラーハンドリングの追加

ユーザーからの入力やメモリ割り当てに関するエラーハンドリングを追加することで、プログラムの堅牢性を向上させます。

ユーザー入力の検証: 入力が整数であるか、奇数であるかを確認し、無効な入力に対して適切なメッセージを表示します。

if (scanf("%d", &size) != 1 || size % 2 == 0) {
    printf("無効な入力です。奇数の整数を入力してください。\n");
    return 1; // エラー終了
}

メモリ割り当ての確認: mallocの戻り値を確認し、メモリ割り当てに失敗した場合はエラーメッセージを表示します。

if (matrix == NULL) {
    printf("メモリの割り当てに失敗しました。\n");
    return 1; // エラー終了
}

ユーザー入力によるサイズ変更対応

プログラムを実行中にユーザーが魔方陣のサイズを変更できるようにすることで、柔軟性を持たせます。

ループによる再入力: ユーザーがサイズを変更したい場合、再度入力を促すループを作成します。

while (1) {
    printf("魔方陣のサイズを入力してください(奇数): ");
    scanf("%d", &size);
    if (size % 2 != 0) {
        break; // 有効なサイズが入力された場合、ループを抜ける
    }
    printf("サイズは奇数でなければなりません。\n");
}