※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

数独を解く


Python環境の準備


Anaconda python のページで、Anaconda pythonをインストールしている前提

今回はnotebookを使います。
ipython notebook --pylab=inline
 

notebook の pylab 環境ではない場合には、ipython を立ち上げて、以下のライブラリ読み出しで pylab が使えるようにします。

from pylab import *
 

プログラム


プログラム中の# は、コメントなので入力しなくても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]]