2014/08/17
R >  数独を解くシミュレーション（1）
既にやっている人がいると思いますが、自分の練習でコードを書きました。単純に左上の空白セルから、総当たり式に候補をストックしていくので効率は悪いです。またグラフィックウィンドウに可視化するため Sys.sleep を入れています。半分くらいセルが埋まった後、候補が一気に絞られてダダッと進むのが何か可笑しい。実行環境は 2014/08/13 の実機を参照。


上の問題は「数独無料ゲーム」 http://www.sudokugame.org/ から拝借しました（2014/08/14 初級）。解いた結果は https://kenpg.up.seesaa.net/image/20140817_sud_2.gif

↓ コード。適当なファイルに保存して実行します。問題データの記法は y-kawaz さんの日記（SQLで数独を解く）に倣いました。同じ問題にこのコードを使うと、とても遅いです。
rm(list=ls())

sud_ini =
'   9  4   327  5  8      32 6187 2 52  591 83 8  6491764  2    719  5324328149756'

main = function(){
	f_plt()
	readline('ENTER to start')
	time_start = proc.time()
	str = sud_ini
	while(1){
		str = f_slv(str)
		if(length(grep(' ', str[1]))==0) break
	}
	message('End')
	print(proc.time() - time_start) }

f_plt = function(){
	pxs = 400
	lty = c(3,3,1)
	if(length(dev.list()) == 0) windows(height=(pxs-45)/96, width=(pxs-8)/96)
	par(plt=rep(0:1, 2))
	plot(c(0.5, 9.5), c(0.5, 9.5), axes=F, type='n', xaxs='i', yaxs='i')
	abline(h=seq(1.5, 8.5, by=1), lty=lty)
	abline(v=seq(1.5, 8.5, by=1), lty=lty)
	f_num(sud_ini, 1) }

f_num = function(sud, col){
	skp = which(unlist(strsplit(sud_ini, '')) != ' ')
	for(i in 1:81){
		xys = f_xys(i)
		n = substr(sud, i, i)
		if(n == ' ' | (col != 1 & is.element(i, skp))) next
		points(xys, cex=4, pch=15, col='white')
		text(xys, cex=1.5, col=col, fon=1, lab=n)
	} }

f_xys = function(loc){
	return(list(
		x = (loc - 1) %% 9 + 1, y = 9 - floor((loc - 1) / 9)
	)) }

f_slv = function(str){
	num = unlist(strsplit(str[1], ''))
	cel = min(grep(' ', num))
	points(f_xys(cel), cex=4, pch=15, col='pink')
	Sys.sleep(0.1)
	for(i in 1:9){
		num2 = replace(num, cel, i)
		if(f_chk(num2) == 0){
			tmp = paste(collapse='', num2)
			f_num(tmp, 2)
			str = c(str, tmp)
		}
	}
	return(str[-1]) }

f_chk = function(num){
	mat = matrix(num, 9, 9, byrow=T)
	vec = gsub(' ', '', c(

		# rows
		apply(mat, 1, function(x){ paste(collapse='', x) })

		# cols
		, apply(mat, 2, function(x){ paste(collapse='', x) })

		# blocks
		, sapply(1:9, function(x){
			z = floor((x - 1) / 3) * 27 + (x - 1) %% 3 * 3 + 1
			z = z + 0:2
			z = c(z, z + 9, z + 18)
			paste(collapse='', num[z])
		})
	))
	chk = sapply(strsplit(vec, ''), function(x){ length(x) - length(unique(x)) })
	return(length(which(chk > 0))) }

main()

↓ 実際の様子。動画は https://kenpg.up.seesaa.net/image/20140817_sud_1.flv



今回のように単純に左上の空白セルから始めるのでなく、絞りやすいセル、上の問題でいえば左下ブロックの一箇所残ったセルから着手する方が効率的で、実装できたら（2）を書きます。
<< 数独を解くシミュレーション（2）
ジャグ配列風 list を行列に変換 >>