数独を解く
Python環境の準備
今回はnotebookを使います。
ipython notebook --pylab=inline
notebook の pylab 環境ではない場合には、ipython を立ち上げて、以下のライブラリ読み出しで pylab が使えるようにします。
プログラム
プログラム中の# は、コメントなので入力しなくてもOK
def checkzero(mm):
# 入力された数列から0値のインデックスリストを作成
rex = []
for i in range(0,len(mm)):
if mm[i] == 0:
rex.append(i)
return rex
def convxy(idx):
# 0 から 80 のインデックスを X,Y 座標に変換
y = int(idx/9)
x = idx - y * 9
return y,x
def cropvar(mm,idx):
# 数独のデータから、横(hval), 縦(vval),ボックス(box)の値を抽出
y,x = convxy(idx)
hval = mm[y,:]
vval = mm[:,x]
bx = int(x/3)*3
by = int(y/3)*3
box = mm[by:by+3,bx:bx+3]
# flatten() は、行列を1次元ベクトルに変換
return box.flatten(),hval,vval,(y-by)*3+(x-bx),y,x
def expectval(j):
# 縦、横、ボックスのリストから出てきていない数値を抽出する
cc = [0,0,0,0,0,0,0,0,0,0]
for i in range(0,9):
for k in range(0,3):
idx = int(j[k][i])
cc[idx] = cc[idx] + 1
#print cc
exlist = []
for cidx in range(1,10):
if cc[cidx] == 0:
exlist.append(cidx)
return exlist
def onevaluefit(ns):
# 対象のセルに対して、出現していない数値が1つだけの場合には、それを当てはめる
zcnt = checkzero(ns.flatten())
#print "onevaluefit : " + str(len(zcnt))
for h in range(0,len(zcnt)):
rex = checkzero(ns.flatten())
if len(rex) == 0:
#print ns
return ns
upcnt = 0
#print "iter:" + str(h) + " rexcnt = " + str(len(rex))
for idx in rex:
j = cropvar(ns,idx)
elis = expectval(j)
#print elis
if len(elis) == 1:
y,x = convxy(idx)
ns[y][x] = elis[0]
upcnt = upcnt + 1
#print x,y,idx,elis[0]
if upcnt == 0:
break
#print nres
return None
def twovaluefit(ns, stage, limitlevel = 3):
# 数値の候補が2つ以上ある場合には、それぞれの数値を設置した場合の仮説を立てて、以降の処理を再帰的に処理する
if stage == limitlevel:
return None
if onevaluefit(ns) is not None:
return ns
# first stage : fit one value
zcnt = checkzero(ns.flatten())
for h in range(0,len(zcnt)):
rex = checkzero(ns.flatten())
if len(rex) == 0:
return ns
upcnt = 0
for idx in rex:
j = cropvar(ns,idx)
elis = expectval(j)
y,x = convxy(idx)
if len(elis) == 1:
ns[y][x] = elis[0]
upcnt = upcnt + 1
# 候補が2つの場合
if len(elis) == 2:
ns1 = ns.copy()
ns2 = ns.copy()
ns1[y][x] = elis[0]
C1 = twovaluefit(ns1,stage+1,limitlevel)
if C1 is not None:
return C1
ns2[y][x] = elis[1]
C2 = twovaluefit(ns2,stage+1,limitlevel)
if C2 is not None:
return C2
if upcnt == 0:
break
return None
テストプログラム
# 問題を設定する。9x9の問題
sudokudata = array([[ 0, 0, 0, 0, 7, 0, 0, 6, 0,], \
[ 3, 0, 0, 9, 0, 0, 1, 0, 0,], \
[ 0, 0, 2, 0, 0, 4, 0, 0, 0,], \
[ 4, 0, 0, 6, 0, 0, 3, 0, 9,], \
[ 1, 0, 0, 0, 4, 0, 0, 0, 2,], \
[ 9, 0, 7, 0, 0, 5, 0, 0, 4,], \
[ 0, 0, 0, 4, 0, 0, 7, 0, 0,], \
[ 0, 0, 4, 0, 0, 6, 0, 0, 3,], \
[ 0, 7, 0, 0, 2, 0, 0, 0, 0,]])
# 答えを格納する sudokucheck としてコピーする(イコールだけだと浅いコピーで元が上書きされる)
sudokucheck = sudokudata.copy()
# 解法。この問題は難しいので結構時間がかかる(10分程度)
# 引数の1番目:問題の9x9のarray
# 引数の2番目:探索の開始カウントとして 0 を入力
# 引数の3番目:仮説を何段まで行うか?初級であれば1で良い。この問題は5段までしないと解けない。
print twovaluefit(sudokucheck,0,5)
答えが表示される
[[8 9 1 3 7 2 4 6 5]
[3 4 6 9 5 8 1 2 7]
[7 5 2 1 6 4 9 3 8]
[4 2 5 6 1 7 3 8 9]
[1 6 3 8 4 9 5 7 2]
[9 8 7 2 3 5 6 1 4]
[2 3 8 4 9 1 7 5 6]
[5 1 4 7 8 6 2 9 3]
[6 7 9 5 2 3 8 4 1]]
最終更新:2013年12月21日 11:13