【Java】数独に使われる魔方陣を出力する

技術記事
【Java】数独に使われる魔方陣を出力する

Javaで数独に使われる9×9の魔方陣をランダムに出力するプログラムを作成してみます。

関連記事

数独魔方陣の特徴

作成する数独の9×9の魔方陣の特徴についてまとめます。

数独の魔方陣の特徴
  • 縦と横の全ての列で1~9の数字が1つずつ使われる
  • 3×3のブロックに1~9の数字が1つずつ使われる

数独の魔方陣はこんな感じの数表です。

$$ \large\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 7 & 2 & 9 & 3 & 6 & 4 & 1 & 5 & 8 \\ \hline 6 & 1 & 5 & 9 & 2 & 8 & 3 & 7 & 4 \\ \hline 3 & 4 & 8 & 7 & 1 & 5 & 6 & 2 & 9 \\ \hline 4 & 9 & 3 & 2 & 8 & 1 & 7 & 6 & 5 \\ \hline 8 & 6 & 1 & 5 & 9 & 7 & 4 & 3 & 2 \\ \hline 2 & 5 & 7 & 4 & 3 & 6 & 9 & 8 & 1 \\ \hline 1 & 7 & 2 & 8 & 4 & 3 & 5 & 9 & 6 \\ \hline 9 & 3 & 6 & 1 & 5 & 2 & 8 & 4 & 7 \\ \hline 5 & 8 & 4 & 6 & 7 & 9 & 2 & 1 & 3 \\ \hline \end{array} $$

プログラミングで作ってみる

上の画像のような数表をランダムで出力するプログラムを作成します。

基本的な作り方のアルゴリズムは以下の通りです。重複のチェックはHashSetを使いました。

アルゴリズム
  1. 出来上がった数表を格納する配列arrayを宣言する
  2. 1~9の数字が入ったArrayListを作りシャッフルし、arrayに格納する（これが横の行の1つになる）
  3. 縦の列に重複しないようにArrayListをarrayに格納していく　重複したら格納せずもう一度シャッフルしていくを繰り返す
  4. 同時に3×3のブロックも重複がないかチェックする　重複したらその都度やり直す

サンプルコードを以下に示します。

MakeSudoku.java
 1import java.util.ArrayList;
 2import java.util.Collections;
 3import java.util.HashSet;
 4import java.util.List;
 5import java.util.Set;
 6
 7public class MakeSudoku {
 8  /** 数独の数字を格納する配列 */
 9  int[][] array = new int[9][9];
10
11  /** 1から9までを格納するArrayList */
12  List<Integer> list = new ArrayList<Integer>();
13
14  /** 重複チェック用のhashSet1 */
15  Set<Integer> hashSet1 = new HashSet<>();
16
17  /** 重複チェック用のhashSet2 */
18  Set<Integer> hashSet2 = new HashSet<>();
19
20  /** 実行用mainメソッド */
21  public static void main(String[] args) {
22    MakeSudoku makeSudoku = new MakeSudoku();
23    makeSudoku.execute();
24    makeSudoku.showArray();
25  }
26
27  /** 数独の作成 */
28  private void execute() {
29    for (int i = 1; i <= 9; i++) {
30      list.add(i);
31    }
32    Collections.shuffle(list);
33
34    for (int i = 0, j; i <= 8;) {
35      int u = 2, v = 2;
36      if (i == 5) {
37        u = 5;
38      }
39
40      for (j = 0; j <= 8;) {
41        array[i][j] = list.get(j);
42        for (int x = 0; x < i; x++) {
43          hashSet1.add(array[x][j]);
44        }
45        if (hashSet1.contains(array[i][j])) {
46          hashSet1.clear();
47          break;
48        }
49        if (i == u && j == v) {
50          hashSet2.add(array[u - 2][v - 2]);
51          hashSet2.add(array[u - 2][v - 1]);
52          hashSet2.add(array[u - 2][v]);
53          hashSet2.add(array[u - 1][v - 2]);
54          hashSet2.add(array[u - 1][v - 1]);
55          hashSet2.add(array[u - 1][v]);
56          hashSet2.add(array[u][v - 2]);
57          hashSet2.add(array[u][v - 1]);
58          hashSet2.add(array[u][v]);
59          if (hashSet2.size() != 9) {
60            hashSet2.clear();
61            i -= 2;
62            j = 0;
63            break;
64          }
65          v = 5;
66
67        }
68        j++;
69
70        hashSet1.clear();
71        hashSet2.clear();
72      }
73      if (j == 9) {
74        i++;
75      }
76
77      Collections.shuffle(list);
78    }
79  }
80
81  /** 配列を数表形式で出力する */
82  private void showArray() {
83    for (int[] a : array) {
84      for (int i : a) {
85        System.out.printf("%3d", i);
86      }
87      System.out.println();
88    }
89  }
90}

実行結果の一例が以下になります。

出力結果（一例）
1  7  3  2  1  4  9  5  6  8
2  5  1  6  3  8  2  9  7  4
3  8  4  9  7  6  5  3  2  1
4  4  2  5  6  9  8  1  3  7
5  6  9  3  4  1  7  8  5  2
6  1  7  8  5  2  3  4  9  6
7  2  8  7  9  5  4  6  1  3
8  9  6  4  2  3  1  7  8  5
9  3  5  1  8  7  6  2  4  9

条件を満たす数表が出力されました。条件を満たすまでシャッフルを繰り返すので、出力されるまでちょっと時間がかかります。

今回は数独の数表を作るところまで完成しました。

完全にランダムで条件を満たすか当てはめていってるので、処理に時間がかかっているところが問題点ですね。その部分を処理を減らすことも考えていきたいです。

この記事では時間がなくてできませんでしたが、数独の問題を作る機能も実装したいと思います。以上で記事を終わりにします。