慶應入試で出題された数独の類似問題のWindokuをPythonで解いてみました。
＋－－－－－＋－－－－－＋－－－－－＋ ｜３ ９ ・｜・ ・ ・｜・ ・ ４｜ ｜ ＋－－－＋－＋ ＋－＋－－－＋ ｜ ｜・｜・ ・｜９｜・｜・｜・ ６｜・｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜・｜・ ・｜３｜１｜・｜５ ・｜９｜ ＋－＋－－－＋－＋－＋－＋－－－＋－＋ ｜２｜７ ・｜・｜・｜・｜９ ・｜・｜ ｜ ＋－－－＋－＋ ＋－＋－－－＋ ｜ ｜８ ・ ・｜・ ２ ９｜・ ・ ・｜ ｜ ＋－－－＋－＋ ＋－＋－－－＋ ｜ ｜・｜・ ９｜・｜・｜７｜３ ・｜・｜ ＋－＋－－－＋－＋－＋－＋－－－＋－＋ ｜・｜・ １｜２｜９｜６｜・ ８｜・｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜ ｜・｜・ ５｜・｜・｜・｜・ ９｜・｜ ｜ ＋－－－＋－＋ ＋－＋－－－＋ ｜ ｜９ ６ ・｜・ ・ ・｜７ ・ ・｜ ＋－－－－－＋－－－－－＋－－－－－＋
前回の数独のプログラムに、「灰色の4個の3×3のマスに1〜9までの数字がすべて現れる」かチェックする部分を書き加えただけです。(^_^;
この「Windoku」は、「Hypersudoku」とか「Four-Box Sudoku」とか「NRC-Sudoku」とも呼ばれているようです。(^_^;
ちなみに、通常の数独のルールだけで解くと、156個の解が見つかって、解は確定しません。
● Windoku1.py
# coding: UTF-8 # Windoku1.py from time import time import itertools # 慶應SFCの入試で出題されたWindoku sQ = ''' 3 9 .|. . .|. . 4 +---+-+ +-+---+ .|. .|9|.|.|. 6|. .|. .|3|1|.|5 .|9 -+---+-+-+-+---+- 2|7 .|.|.|.|9 .|. +---+-+ +-+---+ 8 . .|. 2 9|. . . +---+-+ +-+---+ .|. 9|.|.|7|3 .|. -+---+-+-+-+---+- .|. 1|2|9|6|. 8|. .|. 5|.|.|.|. 9|. +---+-+ +-+---+ 9 6 .|. . .|7 . . ''' ##sQ = '000000010002000034000051000000006500070300080003000000000080000580000900690000000' 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 # 灰色の4個の3×3のマスのチェック flg = True for k in range(4): p,q = 1+k//2*4,1+k%2*4 li = [m[i][j] for i in range(p,p+3) \ for j in range(q,q+3)] if len(set(li))!=9: 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()
●実行結果
[3,9,7,8,6,5,1,2,4] [5,1,4,9,7,2,8,6,3] [6,2,8,3,1,4,5,7,9] [2,7,6,5,4,3,9,1,8] [8,5,3,1,2,9,6,4,7] [1,4,9,6,8,7,3,5,2] [7,3,1,2,9,6,4,8,5] [4,8,5,7,3,1,2,9,6] [9,6,2,4,5,8,7,3,1] Runtime : 0.316 [sec]
※参考URL
●慶應SFCの入試で出題されたWindokuと呼ばれる数独に似た問題の考察
●Cross+A :: 数独 (Sudoku) > ウィンドク（Windoku）
