「数独」の編集履歴（バックアップ）一覧はこちら

「数独」(2013/12/21 (土) 11:13:47) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*数独を解く

**Python環境の準備

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

今回はnotebookを使います。 
#highlight(){
ipython notebook --pylab=inline
}

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

#highlight(python){
from pylab import *
}

** プログラム

プログラム中の# は、コメントなので入力しなくてもOK

#highlight(python){

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() は、行列を１次元ベクトルに変換
    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):
# 対象のセルに対して、出現していない数値が１つだけの場合には、それを当てはめる
    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):
# 数値の候補が２つ以上ある場合には、それぞれの数値を設置した場合の仮説を立てて、以降の処理を再帰的に処理する
    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
 
　　　　　　# 候補が２つの場合
            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

}

** テストプログラム

#highlight(python){

# 問題を設定する。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分程度）
# 引数の１番目：問題の9x9のarray
# 引数の２番目：探索の開始カウントとして 0 を入力
# 引数の３番目：仮説を何段まで行うか？初級であれば１で良い。この問題は５段までしないと解けない。

print twovaluefit(sudokucheck,0,5)

}

答えが表示される

#highlight(python){
[[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]]
}

*数独を解く

**Python環境の準備

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

今回はnotebookを使います。 
#highlight(){
ipython notebook --pylab=inline
}

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

#highlight(python){
from pylab import *
}

** プログラム

プログラム中の# は、コメントなので入力しなくてもOK

#highlight(python){

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() は、行列を１次元ベクトルに変換
    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):
# 対象のセルに対して、出現していない数値が１つだけの場合には、それを当てはめる
    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):
# 数値の候補が２つ以上ある場合には、それぞれの数値を設置した場合の仮説を立てて、以降の処理を再帰的に処理する
    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
 
　　　　　　# 候補が２つの場合
            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

}

** テストプログラム

#highlight(python){

# 問題を設定する。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分程度）
# 引数の１番目：問題の9x9のarray
# 引数の２番目：探索の開始カウントとして 0 を入力
# 引数の３番目：仮説を何段まで行うか？初級であれば１で良い。この問題は５段までしないと解けない。

print twovaluefit(sudokucheck,0,5)

}

答えが表示される

#highlight(python){
[[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]]
}