＋－－－＋－－－＋－－－＋ ｜８・・｜・・・｜・・・｜ ｜・・３｜６・・｜・・・｜ ｜・７・｜・９・｜２・・｜ ＋－－－＋－－－＋－－－＋ ｜・５・｜・・７｜・・・｜ ｜・・・｜・４５｜７・・｜ ｜・・・｜１・・｜・３・｜ ＋－－－＋－－－＋－－－＋ ｜・・１｜・・・｜・６８｜ ｜・・８｜５・・｜・１・｜ ｜・９・｜・・・｜４・・｜ ＋－－－＋－－－＋－－－＋
今更感はありますが、前回の9×9の計算ブロックのとき、数独も順列総当たりで、いけるかもと思ってやってみました。でも、さすがに、それだけではきついので、1番目の参考URLの「確定サーチ」で枝刈りしてみました。(^_^;
ちなみに、本プログラムで、解を一つ見つけると終了するようにしているのは、全部探すと時間がかかってしまうからです。参考URLのプログラムに比べれば、あまり速くはないですが、問題の難易度を反映して時間がかかるので、難易度の判定ぐらいには使えるかも知れません。(^_^;
● Sudoku1.py
# coding: UTF-8 # Sudoku1.py from time import time import itertools # 世界一難しい数独(2012年版) sQ = ''' 8 . . |. . . |. . . . . 3 |6 . . |. . . . 7 . |. 9 . |2 . . ------+------+------ . 5 . |. . 7 |. . . . . . |. 4 5 |7 . . . . . |1 . . |. 3 . ------+------+------ . . 1 |. . . |. 6 8 . . 8 |5 . . |. 1 . . 9 . |. . . |4 . . ''' ##sQ = '800000000003600000070090200050007000000045700000100030001000068008500010090000400' def toStr(lst): return '[%s]'%','.join(['%s'%x for x in lst]) # 列がダブっていないか調べる def isDupClm(n,li2D): m = len(li2D) for i in range(m): for j in range(n): if li2D[n][i]==li2D[j][i]: return True return False # 3ｘ3ブロック内がダブっていないか調べる def isDupBlk(n,li2D): m = n//3 for k in range(3): K = 3*k li = [li2D[i][j] for i in range(3*m,n) for j in range(K,K+3)] for i in range(3): if li2D[n][K+i] in li: return True return False # m行ｎ列目の数があるブロック内のすべての数のリストを取得(ただし0以外) def getBlk(m,n,li2D): m,n = m//3,n//3 li = [li2D[i][j] for i in range(3*m,3*m+3) \ for j in range(3*n,3*n+3) if li2D[i][j]!=0] return li R = range(1,10) # フラグ: 行・列・ブロックのそれぞれで確定している数のリスト rowFlg = [[] for i in range(9)] colFlg = [[] for i in range(9)] blkFlg = [[] for i in range(9)] def mkFlgs(la): for i in range(9): rowFlg[i] = [la[i][k] for k in range(9) if la[i][k]!=0] for j in range(9): colFlg[j] = [la[k][j] for k in range(9) if la[k][j]!=0] for i in range(0,9,3): for j in range(0,9,3): blkFlg[i+j//3] = getBlk(i,j,la) # 各マスの候補のリストを得る def mkCandidateTbl(la): lb = [[[] for i in range(9)] for j in range(9)] mkFlgs(la) for i in range(9): for j in range(9): if la[i][j]!=0: lb[i][j]=[la[i][j]] else: li = rowFlg[i]+colFlg[j]+blkFlg[i//3*3+j//3] lb[i][j] = sorted(set(R)-set(li)) return lb # マスの確定サーチ: 置ける数字がひとつしかないマスを探す def decideCell(la,lb): li = la[:] fd = False for i in range(9): for j in range(9): if la[i][j]!=0: continue if len(lb[i][j])==1: li[i][j] = lb[i][j][0] fd = True if not fd: li = [] return li # 縦方向の確定サーチ: 縦方向で確定できる数字を探す def decideClm(la,lb): li = la[:] fd = False for j in range(9): for m in tuple(set(R)-set(colFlg[j])): c = k = 0 flg = True for i in range(9): if la[i][j]!=0: continue if m in lb[i][j]: c+=1; k = i if c> 1: break else: flg = False if flg: continue if c==1: li[k][j] = m fd = True if not fd: li = [] return li # 横方向の確定サーチ def decideRow(la,lb): li = la[:] fd = False for i in range(9): for m in tuple(set(R)-set(rowFlg[i])): c = k = 0 flg = True for j in range(9): if la[i][j]!=0: continue if m in lb[i][j]: c+=1; k = j if c> 1: break else: flg = False if flg: continue if c==1: li[i][k] = m fd = True if not fd: li = [] return li # ブロックの確定サーチ def decideBlk(la,lb): li = la[:] fd = False for i in range(0,9,3): for j in range(0,9,3): for m in tuple(set(R)-set(blkFlg[i//3*3+j//3])): c = ib = jb = 0 flg = True for k in range(9): if la[i+k//3][j+k%3]!=0: continue if m in lb[i+k//3][j+k%3]: c+=1; ik,jk = i+k//3,j+k%3 if c> 1: break else: flg = False if flg: continue if c==1: li[ik][jk] = m fd = True if not fd: li = [] return li def mkPerm(la): perm = [[] for i in range(9)] while True: flg = True b = mkCandidateTbl(la) li = decideCell(la,b) if li!=[]: la = li[:]; flg = False b = mkCandidateTbl(la) li = decideClm(la,b) if li!=[]: la = li[:]; flg = False b = mkCandidateTbl(la) li = decideRow(la,b) if li!=[]: la = li[:]; flg = False b = mkCandidateTbl(la) li = decideBlk(la,b) if li!=[]: la = li[:]; flg = False b = mkCandidateTbl(la) if flg: break for k in range(9): li = b[k] r = list(set(R)-set([n for n in la[k] if n!=0])) for p in itertools.permutations(r): # Perm[k] p = list(p) for i in range(9): if la[k][i]!=0: p[i:i] = [la[k][i]] flg = True for i in range(9): if la[k][i]!=0: continue if p[i] not in li[i]: break else: flg = False if flg: continue perm[k].append(p) return perm def solver(sq): m = [[0 for i in range(9)] for j in range(9)] a = [[0 for i in range(9)] for j in range(9)] sq = sq.replace('.','0') lq = [c for c in sq if c in '0123456789'] for i in range(9): for j in range(9): a[i][j] = int(lq[9*i+j]) Perm = mkPerm(a) ans = [] for m[0] in Perm[0]: for m[1] in Perm[1]: if isDupClm(1,m): continue if isDupBlk(1,m): continue for m[2] in Perm[2]: if isDupClm(2,m): continue if isDupBlk(2,m): continue for m[3] in Perm[3]: if isDupClm(3,m): continue for m[4] in Perm[4]: if isDupClm(4,m): continue if isDupBlk(4,m): continue for m[5] in Perm[5]: if isDupClm(5,m): continue if isDupBlk(5,m): continue for m[6] in Perm[6]: if isDupClm(6,m): continue for m[7] in Perm[7]: if isDupClm(7,m): continue if isDupBlk(7,m): continue for i in range(9): li = [m[j][i] for j in range(8)] m[8][i] = 45-sum(li) if isDupBlk(8,m): continue flg = True for i in range(9): if a[8][i]==0: continue if a[8][i]!=m[8][i]: break else: flg = False if flg: continue pass # チェックを潜り抜けたものだけを保存 ans.append(m[:][:]) return ans # 1つ見つけたら終了 return ans # 全部探すときは1行上(↑)をコメントアウトしてこちらから出る def main(): tm = time() # Timer Start a = solver(sQ) for i in range(len(a)): for j in range(9): print(toStr(a[i][j])) print('') print("Runtime : %.3f [sec]"%(time()-tm)) # Timer Stop & Disp if __name__ == '__main__': main()
●実行結果
[8,1,2,7,5,3,6,4,9] [9,4,3,6,8,2,1,7,5] [6,7,5,4,9,1,2,8,3] [1,5,4,2,3,7,8,9,6] [3,6,9,8,4,5,7,2,1] [2,8,7,1,6,9,5,3,4] [5,2,1,9,7,4,3,6,8] [4,3,8,5,2,6,9,1,7] [7,9,6,3,1,8,4,5,2] Runtime : 1.018 [sec]
※参考URL
●お気楽Ｃ言語プログラミング超入門 > 数独の解法
●あらゆる数独パズルを解く
●「世界一難しい数独」を瞬間解答するPeter Norvig氏のPythonプログラム
●数独の詳細情報 : Vector ソフトを探す！
●『逃げるは恥だが役に立つ』第10話に出て来た数独 - rscの日記
