この記事では数独に使われる9×9の魔方陣をプログラミングで作成してみます。
数独の魔方陣の特徴
作成する9×9の魔方陣の特徴についてまとめます。
特徴
- 縦と横の全ての列で1~9の数字が1つずつ使われる
- 3×3のブロックに1~9の数字が1つずつ使われる
数独の魔方陣はこんな感じの数表です。
プログラミングで作ってみる
上の画像のような数表を出力するプログラムを作成します。
アルゴリズム
基本的な作り方は
アルゴリズム
- 出来上がった数表を格納するint型配列num[9][9]を宣言する
- 1~9の数字が入ったArrayListを作りシャッフルしnumに格納する（これが横の行の1つになる）
- 縦の列に重複しないようにArrayListをnumに格納していく 重複したら格納せずもう一度シャッフルしていくを繰り返す
- 同時に3×3のブロックも重複がないかチェックする 重複したらその都度やり直す
この様なアルゴリズムで作成することにします。重複のチェックはHashSetを使いました。
サンプルコード
サンプルコードを以下に示します。
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
public class Sudoku_make {
public static void main(String[] args) {
// num:数表 list:横の行
// integerSet1:縦の重複の確認用
// integerSet2:3×3ブロックの重複の確認用
int[][] num = new int[9][9];
ArrayList<Integer> list = new ArrayList<Integer>();
Set<Integer> integerSet1 = new HashSet<>();
Set<Integer> integerSet2 = new HashSet<>();
int i, j, x;
// listの作成とシャッフル
for (i = 1; i <= 9; i++) {
list.add(i);
}
Collections.shuffle(list);
for (i = 0; i <= 8;) {
int u = 2, v = 2;
if (i == 5) {
u = 5;
}
// integerSet1の重複チェック
for (j = 0; j <= 8;) {
num[i][j] = list.get(j);
for (x = 0; x < i; x++) {
integerSet1.add(num[x][j]);
}
if (integerSet1.contains(num[i][j])) {
integerSet1.clear();
break;
}
// integerSet2の重複チェック
if (i == u && j == v) {
integerSet2.add(num[u - 2][v - 2]);
integerSet2.add(num[u - 2][v - 1]);
integerSet2.add(num[u - 2][v]);
integerSet2.add(num[u - 1][v - 2]);
integerSet2.add(num[u - 1][v - 1]);
integerSet2.add(num[u - 1][v]);
integerSet2.add(num[u][v - 2]);
integerSet2.add(num[u][v - 1]);
integerSet2.add(num[u][v]);
if (integerSet2.size() != 9) {
integerSet2.clear();
i -= 2;
j = 0;
break;
}
v = 5;
}
j++;
integerSet1.clear();
integerSet2.clear();
}
if (j == 9) {
i++;
}
Collections.shuffle(list);
}
// 完成したnumの出力
for (i = 0; i <= 8; i++) {
for (j = 0; j <= 8; j++) {
System.out.print(num[i][j] + " ");
}
System.out.println();
}
}
}出力結果（一例）
サンプルコードの出力結果を以下に示します。出力結果は一例です。
3 9 6 7 1 5 2 4 8 2 1 8 6 3 4 5 9 7 7 5 4 8 9 2 1 3 6 5 6 9 3 2 8 4 7 1 1 8 7 4 6 9 3 5 2 4 3 2 1 5 7 6 8 9 8 7 1 5 4 6 9 2 3 6 2 5 9 7 3 8 1 4 9 4 3 2 8 1 7 6 5
条件を満たす数表が出力されました。条件を満たすまでシャッフルを繰り返すので、出力されるまでちょっと時間がかかります。
まとめ
今回は数独の数表を作るところまで完成しました。
完全にランダムで条件を満たすか当てはめていってるので、処理に時間がかかっているところが問題点ですね。その部分を処理を減らすことも考えていきたいです。
この記事では時間がなくてできませんでしたが、数独の問題を作る機能も実装したいと思います。