English

blog

数独解法プログラム 数独の解の見つけ方

数独解法プログラム

この記事では、再帰法を用いた数独の解を見つけ方について説明します。まずコードを使わず、図を見ながら考え方から入ります。その後、Javaコードをお見せします。この解決法は白紙の状態からだけではなく、埋められているマスがあっても、この時点で正しい組み合わせであれば解を見つけてくれます。

こちらからデモプログラムをダウンロードできます。Javaのソース・プロジェクトはGithubから落とせます。ちなみにこのページの下に載せてあるのは解を見つけるために必要なメソッドだけです。

考え方

1. 左上のマスから始めます。左から右へ、上から下へ、というふうに一マスずつ進んでいきます。

2. もし、このマスが右下の最後のマスを訪れた後なら、現在のマスは[9][0]になります。この行が9なら、「全てのマスを通った」という意味のtrueの値を返します。メソッドの中でまずこれを確かめます。

3. 1から9の9つの数字を配列に重複がないよう用意する。再帰メソッドの中でマスの候補として一つずつテストしていきます。


4. 現在のインデックスの数字が、列・行・3x3のブロックのいずれかにすでに入っているかチェックします。

4a. もし入っていなければ、この数字をこのマスに代入します。

次のマスへ移動しましょう(再帰メソッドを呼ぶ)。新しいメソッドの中からまた始まるので、ステップ2から処理を行います。

5. もしこの数字がすでに入っていれば、次の数字を試します。

6. 9つ全ての数字を回った後、どの数字も当てはまらなかったという事なので、falseの値を返して前のメソッドに戻ります。こうやって進んだ道を戻る事をバックトラッキングといいます。

4b. 次のマスから戻った直後の処理です。このマスに一度数字を入れたので、次の数字を試すためにマスの中の数字を初期化します。そしてステップ5から残りの次の数字を試していってください。

実装

解き始める前にまず、現在の数独が解く事のできる組み合わせであるのかどうかを確かめる事を推奨します。ここでは、Javaのコードを部分的に見ながら説明していきます。解を見つける処理に使うメソッドは下の方に載せてあります。こちらではソースコードをプロジェクト単位で載せてます。実際に自分で動かしてみたい方はどうぞ。

これは上記のステップ2に該当します。全ての数字を通り終えたのなら、trueを返す事で再帰からでましょう。

1
2
if (row == 9)
	return true;

もしこのマスが空白ではなく数字が予め入っているなら、無視して次のマスへ移行します。

1
2
3
4
if (cells[row][col] != 0) {
	if (solve(col == 8? (row + 1): row, (col + 1) % 9))
		return true;
}

elseに入った場合、このマスは空白という事なので重複のない、ランダムに並んだ9つの数字の配列を生成します。そしてfor loopで回して一つずつ数字を当てはまるか試していきます。もし現在のインデックスの数字が行・列・3x3ブロックに入っていないなら、この数字をこのマスに代入して次のマスへ移動するために次のマスの行と列を引数として再帰メソッドを呼びます。

後程、解き終わったのかそうでないのか伝えるために、このメソッドのこの行に戻る事になります。解き終わっていなくて(false)下記のコード12行目に戻った場合は次のマスに当てはめられる数字がなかったという事なので、このマスに他に数字が当てはまるか見直す事になります(バックトラッキング)。14行目のelseに入り、マスを初期化してfor loopの次のインデックスに進み、残りの数字を試していきます。どの数字もダメだった場合はfor loopを抜けて22行目のreturn falseを実行します。つまりここで、このメソッドを呼んだ場所へ戻ります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
else {
	// ランダムの数字 1 - 9
	Integer[] randoms = generateRandomNumbers();
	for (int i = 0; i < 9; i++) {
 
		// この行・列・3x3ブロックにこの数字が重複しなければ、このマスにrandoms[i]を代入します。
		if (!containedInRowCol(row, col, randoms[i]) && !containedIn3x3Box(row, col, randoms[i])) {
			cells[row][col] = randoms[i];
			fields[row][col].setText(String.valueOf(randoms[i]));
 
			// 次のマス(左から右へ、上から下へという順)に進む。
			if (solve(col == 8? (row + 1) : row, (col + 1) % 9))
				return true;
			else { // 次のマスに入る数字がなく、このマスに別の数字を入れないといけないので、一度入れた数字を初期化する。
				cells[row][col] = 0;
				fields[row][col].setText("");
			}
		}
	}
}
 
return false;




サンプルコード

これらのメソッドは数独の解を見つけるのに使用したものです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 再帰法で数独の解を見つける。
 * @param row 現在の行のインデックス
 * @param col 現在の列のインデックス
 * @return true もし最後のマスの次のマスにたどり着いたなら。
 */
private boolean solve(int row, int col) {
	// 最終地点まで行ったら、メソッドを全て閉じていく。
	if (row == 9)
		return true;
 
	// もしこのマスが固定されているなら、スキップして次のマスへ。
	if (cells[row][col] != 0) {
		if (solve(col == 8? (row + 1): row, (col + 1) % 9))
			return true;
	} else {
		// ランダムの数字 1 - 9
		Integer[] randoms = generateRandomNumbers();
		for (int i = 0; i < 9; i++) {
 
			// この行・列・3x3ブロックにこの数字が重複しなければ、このマスにrandoms[i]を代入します。
			if (!containedInRowCol(row, col, randoms[i]) && 
					!containedIn3x3Box(row, col, randoms[i])) {
				cells[row][col] = randoms[i];
				fields[row][col].setText(String.valueOf(randoms[i]));
 
				// 次のマス(左から右へ、上から下へという順)に進む。
				if (solve(col == 8? (row + 1) : row, (col + 1) % 9))
					return true;
				else { // 次のマスに入る数字がなく、このマスに別の数字を入れないといけないので、一度入れた数字を初期化する。
					cells[row][col] = 0;
					fields[row][col].setText("");
				}
			}
		}
	}
 
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * valueがこのマスの3x3ブロックに入っているか調べる。
 * @param row 現在の行のインデックス
 * @param col 現在の列のインデックス
 * @return true valueがこのマスの3x3ブロックにすでに存在する場合。
 */
private boolean containedIn3x3Box(int row, int col, int value) {
	// このマスの位置から、3x3ブロックの一番左上のインデックスを計算。
	int startRow = row / 3 * 3;
	int startCol = col / 3 * 3;
 
	// 3x3ブロックの中のこのマス以外を調べる。
	for (int i = startRow; i < startRow + 3; i++)
		for (int j = startCol; j < startCol + 3; j++) {
			if (!(i == row && j == col)) {
				if (cells[i][j] == value){
					return true;
				}
			}
		}
 
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * valueがこのマスの行・列に入っているか調べる。
 * 解を見つける際に使います。
 * @param row 現在の行のインデックス
 * @param col 現在の列のインデックス
 * @param value このマスの値(数字)
 * @return true valueがこのマスの行・列にすでに存在する場合。
 */
private boolean containedInRowCol(int row, int col, int value) {
	for (int i = 0; i < 9; i++) {
		// 同じマスは調べない。
		if (i != col)
			if (cells[row][i] == value)
				return true;
		if (i != row)
			if (cells[i][col] == value)
				return true;
	}
 
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 1から9の9つの数字をランダムな順番・重複のないよう生成する。
 * @return ランダムに並んだ重複のない9つの数字配列
 */
private Integer[] generateRandomNumbers() {
	ArrayList<Integer> randoms = new ArrayList<Integer>();
	for (int i = 0; i < 9; i++)
		randoms.add(i + 1);
	Collections.shuffle(randoms);
 
	return randoms.toArray(new Integer[9]);
}

Leave a Comment