数独の問題を作成してみる

暇だったから数独の問題を作成するプログラムを作成してみる。

数独（すうどく・SUDOKU）とは、3×3のブロックに区切られた9×9の正方形の枠内に1〜9までの数字を入れるペンシルパズルの一つである。
（略）
ルール

空いているマスに1〜9のいずれかの数字を入れる。

縦・横の各列及び、太線で囲まれた3×3のブロックに同じ数字が複数入ってはいけない。

数独 - Wikipedia

結果保存用の変数の宣言

まずは、９×９の正方形を作成するということで、問題となる値の代入用に配列を作成する。

var result = Array();
for(var i=1; i<=9; i++) {
	result[i] = Array();
}

判定系の関数の作成

問題を作成する上で、最低でも必要だと考えられる判定形の関数を作成する。

縦に値が無いかを確認

チェックする値をnumとして渡して、その縦列に同じ値が無いかをチェックする。値があったらfalse、値が無かったらtrueが返却される。

function y_check(num, x, y) {

	var flg = true;

	for(var i=1; i<=9 ;i++) {
		if(result[i][x] == num) {
			flg = false;
		}
	}

	return flg;
}

横に値が無いかを確認

縦と同じ要領で、横チェック関数の作成。

function x_check(num, x, y) {

	var flg = true;

	for(var i=1; i<=9 ;i++) {
		if(result[y][i] == num) {
			flg = false;
		}
	}

	return flg;
}

ブロックに値が無いかを確認

渡ってきた座標を元に、どこのブロックに当たるかを確認し、そのブロック内に値が無いことを確認する。返答の方法は上と一緒。

function b_check(num, x, y) {

	var flg = true;

	var x_start = x - ((x - 1) % 3);
	var y_start = y - ((y - 1) % 3);

	for(var i=x_start; i<x_start+3 ;i++) {
		for(var j=y_start; j<y_start+3 ;j++) {
			if(result[j][i] == num) {
				flg = false;
			}
		}
	}

	return flg;
}

空きチェック

どの座標に数字が入っていないかをチェックする。そのために、まずは結果代入用変数の初期化関数を作成する。

function result_init() {
	for(var i=1; i<=9; i++) {
		for(var j=1; j<=9; j++) {
			result[i][j] = 0;
		}
	}
}

で、値が入っていない行をランダムに詰め込んで返答する関数を作成する。

function s_check(num, y) {

	var ret = Array();

	for(var i=1; i<=9; i++) {
		if(result[y][i] != 0){
			ret.push(i);
		}
	}

	var n = ret.length;
	while (--n) {
		var k = Math.floor(Math.random() * n);
		var temp = ret[n];
		ret[n] = ret[k];
		ret[k] = temp;
	}

	return ret;
}

これで9割ぐらい完成。

組み立て

数独の問題としてできるものを一回で求めるプログラムのアルゴリズムを考えるのは非常にめんどくさい。だから、成功するまで初期化して繰り返すプログラムを作成してみる。

function main() {

	var flg = true;

	while(flg) {

		result_init();
		flg = false;

		for(var num=1; num<=9; num++) {

			for(var y=1; y<=9; y++) {

				// 現在あいている場所の取得
				var space = s_check(num, y);

				// 値の代入座標の決定
				var len = space.length;
				while(len) {
					var x = space.pop();
					var x_flg = x_check(num, x, y);
					var y_flg = y_check(num, x, y);
					var b_flg = b_check(num, x, y);
					if(x_flg && y_flg && b_flg) {
						result[y][x] = num;
						break;
					}
					len--;
				}

				// 値が入れれない箇所があった場合、もう一回動かす
				if(len == 0) {
					flg = true;
				}
			}
		}
	}

}

まとめ

うろ覚えで書いたからあっているかどうかは分からないけど、こんな感じで動くはず。これだと全部が入力されている状態でしか出来ないから、もうちょっと修正が必要と考えられる。

解答のアルゴリズムを考え出す。
全部が入力されているものから、いくつか数字を抜いて他を消す。
解答のアルゴリズムで解答を導き出す。
3回ぐらい試して全部同じ値になったらそれが問題になる。

こんな感じかな？今度時間があるときにでも作成してみる。