【Java】ランダムな4×4の魔方陣をプログラミングで作ってみる

皆さんは魔方陣と言われるものをご存知でしょうか？

今回はJavaを使って4×4の「16マス魔方陣」（1～16の数字を1つずつ使ったもの）で作成してみたいと思います。なお、プログラムでは「実行する度にランダムな魔方陣を生成すること」を目標にします。

魔方陣のついての概要

魔方陣とは、以下のような「縦・横・斜めの全ての列について、合計が同じ数になる数字の表」のことをいいます。今回は1～16の数字を一つずつ使ったものを作っていきます。下に魔方陣の一例を示します。

画像の魔方陣では、縦・横・斜めのどの列も合計が「34」になっていることが分かります。この性質を利用して、段階を踏みながらこのような表を出力してみます。

魔方陣を作成するアルゴリズムの概要

具体的な魔方陣作成のアルゴリズムについて示します。

listの作成と2次元配列の出力

実際に上のアルゴリズムをJavaで実装してみましょう。

まずArrayListで1～16が格納されたlistを作り、それをCollectionsクラスのshuffleメソッドでシャッフルします。（ArrayListクラスとshuffleメソッドについてはそれぞれ下の記事にまとめています）

次に、4×4の配列numを数表として表示させます。実行時の空白を揃えるためにprintfメソッドを使用しています。

サンプルコードと出力結果

サンプルコードShowMagicSquareArrayクラスを作成しました。サンプルコードとその出力結果（一例）を以下に示します。

package bg;

import java.util.ArrayList;
import java.util.Collections;

//シャッフルされたlistと数表を出力する
public class ShowMagicSquareArray {
    
    ArrayList<Integer> list = new ArrayList<Integer>();
    int num[][] = new int[4][4];

    public static void main(String[] args) {

        ShowMagicSquareArray sArray = new ShowMagicSquareArray();

        sArray.generateList(sArray);
        System.out.println(sArray.list);

        sArray.showMagicSquare();
    }

    // 1～16が格納された配列listを作りシャッフルする
    void generateList(ShowMagicSquareArray sArray) {
        for (int i = 1; i <= 16; i++) {
            list.add(i);
        }
        Collections.shuffle(list);
    }

    // 4×4の配列numを数表として出力する
    void showMagicSquare() {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                System.out.printf("%3d", num[i][j]);
            }
            System.out.println();
        }
    }

}

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

listの要素がシャッフルされているのが分かります。その下に数表の方である4×4の表が出力されました。これから魔方陣となる表を作っていきます。

魔方陣となる表をシャッフルし続けて求める

とりあえず前準備はできました。それでは先ほどのコードを利用して、魔方陣となる表を出力していきます。

サンプルコードと出力結果

サンプルコードShowMagicSquare44クラスを作成しました。先ほどのShowMagicSquareArrayクラスを継承しています。サンプルコードとその出力結果（一例）を以下に示します。またどれくらい処理を繰り返しているか調べるために、shuffleメソッドの箇所に変数countを設置して出力させています。

package bg;

import java.util.ArrayList;
import java.util.Collections;

public class ShowMagicSquare44 extends ShowMagicSquareArray {

    ArrayList<Integer> list = new ArrayList<Integer>();
    int num[][] = new int[4][4];
    int count = 0;

    public static void main(String[] args) {

        ShowMagicSquare44 sMagicSquare44 = new ShowMagicSquare44();
        
        sMagicSquare44.checkMagicSquare(sMagicSquare44);
        
        System.out.println("シャッフル回数:"+sMagicSquare44.count);
    }

    void checkMagicSquare(ShowMagicSquare44 sMagicSquare44) {

        sMagicSquare44.generateList(sMagicSquare44);
        while (num[0][0] == 0) {

            list.clear();
            sMagicSquare44.generateList(sMagicSquare44);
            list = super.list;

            for (int i = 0; i < 4;) {
                for (int j = 0; j < 4; j++) {
                    num[i][j] = list.get(j);
                }

                // 横の行の合計値をチェック
                if (mahou4_sumcheck(num[i][0], num[i][1], num[i][2], num[i][3])) {
                    for (int j = 0; j < 4; j++) {
                        list.remove(0);
                    }
                    i++;
                } else {
                    Collections.shuffle(list);
                    count++;
                }
            }

            // 縦の列の合計値をチェック
            if (!mahou4_sumcheck(num[0][0], num[1][0], num[2][0], num[3][0])) {
                continue;
            }
            if (!mahou4_sumcheck(num[0][1], num[1][1], num[2][1], num[3][1])) {
                continue;
            }
            if (!mahou4_sumcheck(num[0][2], num[1][2], num[2][2], num[3][2])) {
                continue;
            }
            if (!mahou4_sumcheck(num[0][3], num[1][3], num[2][3], num[3][3])) {
                continue;
            }
            num = diagonallyCheck(num);
            if (num == null) {
                continue;
            }
            break;

        }
        super.num = num;
        sMagicSquare44.showMagicSquare();
    }

    // 斜めの合計値をチェック
     int[][] diagonallyCheck(int num[][]) {
        int count = 0;
        ArrayList<Integer> list = new ArrayList<Integer>();
        int num2[][] = new int[4][4];
        for (int i = 0; i < 4; i++) {
            list.add(i);
        }
        while (true) {
            Collections.shuffle(list);
            count++;
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    num2[i][j] = num[list.get(i)][j];
                }
            }
            if (count >= 50) {
                num2[0][0] = 0;
                return num2;
            }
            if (!mahou4_sumcheck(num2[0][0], num2[1][1], num2[2][2], num2[3][3])) {
                continue;
            }
            if (!mahou4_sumcheck(num2[0][3], num2[1][2], num2[2][1], num2[3][0])) {
                continue;
            }
            break;
        }
        return num2;
    }

    // 合計値が34であるか判定する
     boolean mahou4_sumcheck(int num1, int num2, int num3, int num4) {
        if (num1 + num2 + num3 + num4 == 34) {
            return true;
        } else {
            return false;
        }
    }
}

  6 12  2 14
 10 15  6  3
 12  9  4  9
 16 13  1  4
シャッフル回数:131

これで4×4の魔方陣の完成です。解が見つかるまでループするため、何度か実行して確認するとシャッフル回数は30～150回程度行われていました。

まとめ

今日やったことのまとめ（感想）です。

非常に長くて分かりづらいコードになってしまいましたが、今の自分のスキルではこれが限界でした…。まあやりたいことは実現できたのでこれは良しとします。今度はより分かりやすく書けるよう挑戦したいですね！ 以上で記事を終わりにします。