皆さん【おすすめの曲】の質問の回答ありがとうございました。ご紹介いただいたものはどれもすばらしいものばかりでした。ベストアンサーは、個人的な好みで決めました。(^_^;
ベストアンサーの方のご紹介をヒントにして、ベートーヴェンの「月光ソナタ」を検索してみたら、いいのが見つかりました。o(^-^)o
●LoLa & Hauser - Moonlight Sonata
慶應入試で出題された数独の類似問題の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）
＋－－－＋－－－＋－－－＋ ｜８・・｜・・・｜・・・｜ ｜・・３｜６・・｜・・・｜ ｜・７・｜・９・｜２・・｜ ＋－－－＋－－－＋－－－＋ ｜・５・｜・・７｜・・・｜ ｜・・・｜・４５｜７・・｜ ｜・・・｜１・・｜・３・｜ ＋－－－＋－－－＋－－－＋ ｜・・１｜・・・｜・６８｜ ｜・・８｜５・・｜・１・｜ ｜・９・｜・・・｜４・・｜ ＋－－－＋－－－＋－－－＋
今更感はありますが、前回の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の日記
何かいい感じなので、はってみました。(^_^;
●米津玄師 MV「Lemon」
P.S.
皆さん、質問の回答・コメント有難うございました。
男性曲を女性が歌うのも何かいい感じですよね。それから、質問をもう少し広くして、「好きなカバー曲を教えてください」に問題を変えた方が良かったかも知れません。(^_^;
※参考URL
http://q.hatena.ne.jp/1524748149
ネットで見つけた計算ブロックの問題をPythonで解いてみました。(^_^;
ルールの概要は次の通りです。前回は和でしたが、今回は積と商を使います。
①１〜９までの数字…(ry
②太線で囲まれたブロック内のマスが2つのとき、ブロック内に書かれた数字はマスに入る数字の積または商を表す。
③太線で囲まれたブロック内のマスが3つ以上のとき、ブロック内に書かれた数字はマスに入る数字の積を表す。
0 1 2 3 4 5 6 7 8 +---+---+---+---+---+---+---+---+---+ 0 |72 |50 |28 |54 |2 |24 | +---+---+---+ + +---+ + + + 1 |294 | | |72 | | | | +---+ +---+---+---+ +---+---+ + 2 |576| |42 |15 | |4 | | + +---+ +---+---+---+---+---+ + 3 | | |24 |10 | | +---+---+---+---+---+---+---+---+---+ 4 |24 |2 |432 |12 |35 | + + +---+---+---+---+---+---+---+ 5 | | |252 |30 |432 | + +---+---+---+---+---+ + +---+ 6 | |48 |3 |35 | | |63 | +---+---+---+---+ + +---+---+ + 7 |120 | | |4 | | +---+---+---+---+---+---+---+---+---+ 8 |20 |3 |3 |56 | +---+---+---+---+---+---+---+---+---+
ただし、外側の数字は、プログラム用の配列のインデックスです。
今回は、さすがに「Perm = [list(itertools.permutations(R))]*8」で回すのは大変なので、各ループを必要条件で絞り込んでみました。例えば、上の[0][3]の位置に入る数は、50の約数である必要があります。
よって、これを用いて、プログラム中の「if 50%p[3]!=0: continue」のようにして、Perm[0]の候補を絞り込みました。
ちなみに、このブロックは、縦横違う数字という条件より、m[0][3]=5,m[1][3]=2,m[1][2]=5と決定するのですが、そこまでは使いませんでした。(^_^;
この他にも、3つのマスからなるL型および逆L型のもので、ブロック内に書かれた数字が2,3,294,576などのものも決定することができます。こういうのも使うと、もう少し速くなります。(^_^;
● CalcBlocks2.py
# coding: UTF-8 # CalcBlocks2.py from time import time import itertools def toStr(lst): return '[%s]'%','.join(['%s'%x for x in lst]) # 列がダブっていないか調べる def isDuplicated(n,li2D): m = len(li2D) for i in range(m): li = [li2D[j][i] for j in range(n)] if len(set(li))!=n: return True return False def chk2Cells(a,b,c): if a*b==c: return True l,s = max(a,b),min(a,b) return l%s==0 and l//s==c def main(): tm = time() # Timer Start m = [[0]*9]*9 R = range(1,10) ## Perm = [list(itertools.permutations(R))]*8 Perm = [[],[],[],[],[],[],[],[]] for p in itertools.permutations(R): # Perm[0] if p[0]*p[1]*p[2]!= 72: continue if 50%p[3]!=0: continue if 28%p[4]!=0: continue if 54%(p[5]*p[6])!=0: continue if 24%p[8]!=0: continue Perm[0].append(p) for p in itertools.permutations(R): # Perm[1] if 294%(p[0]*p[1])!=0: continue if 50%(p[2]*p[3])!=0: continue if 28%p[4]!=0: continue if 72%p[5]!=0: continue if 54%p[6]!=0: continue if 24%p[8]!=0: continue Perm[1].append(p) for p in itertools.permutations(R): # Perm[2] if 576%p[0]!=0: continue if 294%p[1]!=0: continue if 42%p[2]!=0: continue if p[3]*p[4]!=15: continue if 72%p[5]!=0: continue if 24%p[8]!=0: continue Perm[2].append(p) for p in itertools.permutations(R): # Perm[3] if 576%(p[0]*p[1])!=0: continue if 42%p[2]!=0: continue if p[3]*p[4]!=24: continue if p[5]*p[6]*p[7]!=10: continue if 24%p[8]!=0: continue Perm[3].append(p) for p in itertools.permutations(R): # Perm[4] if 24%p[0]!=0: continue if 2%p[1]!=0: continue if p[2]*p[3]*p[4]!=432: continue if p[5]*p[6]!=12: continue if p[7]*p[8]!=35: continue Perm[4].append(p) for p in itertools.permutations(R): # Perm[5] if 24%p[0]!=0: continue if 2%(p[1]*p[2])!=0: continue if p[3]*p[4]*p[5]!=252: continue if 30%p[6]!=0: continue if 432%(p[7]*p[8])!=0: continue Perm[5].append(p) for p in itertools.permutations(R): # Perm[6] if 24%p[0]!=0: continue if p[1]*p[2]*p[3]!=48: continue if 3%p[4]!=0: continue if 35%p[5]!=0: continue if 30%p[6]!=0: continue if 432%p[7]!=0: continue if 63%p[8]!=0: continue Perm[6].append(p) for p in itertools.permutations(R): # Perm[7] if p[0]*p[1]*p[2]!=120: continue if 3%(p[3]*p[4])!=0: continue if 35%p[5]!=0: continue if 63%p[8]!=0: continue Perm[7].append(p) ## for n in range(8): print(len(Perm[n])) ## exit() for m[0] in Perm[0]: ## if m[0][0]*m[0][1]*m[0][2]!= 72: continue for m[1] in Perm[1]: if m[0][3]*m[1][2]*m[1][3]!= 50: continue if m[0][4]*m[1][4]!= 28: continue if m[0][5]*m[0][6]*m[1][6]!= 54: continue if not chk2Cells(m[0][7],m[1][7],2): continue if isDuplicated(2,m): continue for m[2] in Perm[2]: if m[1][0]*m[1][1]*m[2][1]!=294: continue ## if m[2][3]*m[2][4]!= 15: continue if m[1][5]*m[2][5]!= 72: continue if not chk2Cells(m[2][6],m[2][7],4): continue if isDuplicated(3,m): continue for m[3] in Perm[3]: if m[2][0]*m[3][0]*m[3][1]!=576: continue if m[2][2]*m[3][2]!= 42: continue ## if m[3][3]*m[3][4]!= 24: continue ## if m[3][5]*m[3][6]*m[3][7]!= 10: continue if m[0][8]*m[1][8]*m[2][8]*m[3][8]!= 24: continue if isDuplicated(4,m): continue for m[4] in Perm[4]: ## if m[4][2]*m[4][3]*m[4][4]!=432: continue ## if m[4][5]*m[4][6]!= 12: continue ## if m[4][7]*m[4][8]!= 35: continue if isDuplicated(5,m): continue for m[5] in Perm[5]: if m[4][1]*m[5][1]*m[5][2]!= 2: continue ## if m[5][3]*m[5][4]*m[5][5]!=252: continue if isDuplicated(6,m): continue for m[6] in Perm[6]: if m[4][0]*m[5][0]*m[6][0]!= 24: continue ## if m[6][1]*m[6][2]*m[6][3]!= 48: continue if m[5][6]*m[6][6]!= 30: continue if m[5][7]*m[5][8]*m[6][7]!=432: continue if isDuplicated(7,m): continue for m[7] in Perm[7]: ## if m[7][0]*m[7][1]*m[7][2]!=120: continue if m[6][4]*m[7][3]*m[7][4]!= 3: continue if m[6][5]*m[7][5]!= 35: continue if m[6][8]*m[7][8]!= 63: continue if not chk2Cells(m[7][6],m[7][7],4): continue if isDuplicated(8,m): continue for i in range(9): li = [m[j][i] for j in range(8)] m[8][i] = 45-sum(li) if m[8][0]*m[8][1]!= 20: continue if m[8][6]*m[8][7]*m[8][8]!= 56: continue if not chk2Cells(m[8][2],m[8][3],3): continue if not chk2Cells(m[8][4],m[8][5],3): continue # チェックを潜り抜けたものだけを表示 for n in range(9): print(toStr(m[n])) print("Runtime : %.3f [sec]"%(time()-tm)) # Timer Stop & Disp if __name__ == '__main__': main()
●実行結果
[1,9,8,5,7,2,3,6,4] [7,6,5,2,4,8,9,3,1] [8,7,6,3,5,9,1,4,2] [9,8,7,4,6,1,2,5,3] [2,1,9,6,8,3,4,7,5] [3,2,1,7,9,4,5,8,6] [4,3,2,8,1,5,6,9,7] [6,5,4,1,3,7,8,2,9] [5,4,3,9,2,6,7,1,8] Runtime : 2.125 [sec]
※参考URL
●判断推理のダンスのペアの問題をPythonで解いてみた。
●計算ブロックの問題をPythonで解いてみた。
拙ブログの記事『Zebra PuzzleをPythonで解いてみた。』の続きです。前回のプログラムにマトリクス(グリッド)表を付けてみました。(^_^;
大きなマトリクス表を描いてみたかったので作ってみましたが、ラベルが半角英数字だったので対策を講じることになりました。2番目の参考URLを参考にして、全角文字を2文字としてカウントするlenB()関数を作りました。これを使って、半角1文字のときは前に空白を補うことにしました。
それから、Python2では、unicodedata.east_asian_width()関数を使うためには引数をユニコード文字列に変換しておく必要があるようです。
ちなみに、今日で、「書いた日数」が500日になります。プラチナまであと半分まで来ました。まだまだ先は長いねぇ。(^_^;
● Zebra2.py
# coding: UTF-8 # Zebra2.py ''' H: 12345 C: YBRWG N: NUESJ D: WTMOC S: KCOLP P: FHSDZ ''' import itertools from time import time import unicodedata import sys def lenB(s): if sys.version_info[0]==2: s = unicode(s) # Python3では不要 w = 0 for c in s: d = unicodedata.east_asian_width(c) w+=(1 if d in 'HNa' else 2) return w # ラベルと答えのリスト等からマトリクス表を作成 def mkMatTbl(lbl,ans): m,n = len(lbl),len(lbl[0]) li = [lbl[i] for i in range(1,m)] # 横軸ラベルの作成 s = ' ' for i in range(m-1): for j in range(n): t = li[i][j] if not isinstance(t,int): if lenB(t)==1: s+=" " s+=t else: s+=('%2s'%str(t))[:2] print(s) for h in range(m-1): for i in range(n): s,t = '',lbl[-h][i] if not isinstance(t,int): # 縦軸ラベルの作成 if lenB(t)==1: s+=' ' s+=t else: s = ('%2s'%str(t))[:2] g = ans[-h].index(t) for j in range(1,m-h): a = ans[j][g] for k in range(n): s+=' o' if lbl[j][k]==a else ' x' print(s) # 条件チェック： xからm個右側にyがあるか調べる def check_cond(m, a, x, b, y): n = a.index(x) if n==ValueError or len(a)<=m+n: return False return b[m+n]==y # マッチング条件 def check_match(a, x, b, y): return check_cond(0, a, x, b, y) # 順序付き隣接条件(左からx,yの順で隣接) def check_adj_1(a, x, b, y): return check_cond(1, a, x, b, y) # 隣接条件(順不定) def check_adj_2(a, x, b, y): return check_adj_1(a,x,b,y) or check_adj_1(b,y,a,x) def main(): tm = time() # Timer Start # 要素を昇順にソートしたもの HOUSE = '12345' # 家の場所(固定) COLOR = 'BGRWY' # 家の色 NATION = 'EJNSU' # 国、国籍 DRINK = 'CMOTW' # 飲み物 SMOKE = 'CKLOP' # タバコ PET = 'DFHSZ' # ペット # 連想配列 Nation = { "E" : u"E:イギリス", "J" : u"J:日本", "N" : u"N:ノルウェー", "S" : u"S:スペイン", "U" : u"U:ウクライナ" } house = HOUSE[:] for nation in itertools.permutations(NATION): # nation loop if not check_match(nation,'N',house, '1'): continue # 条件10 for color in itertools.permutations(COLOR): # house loop if not check_match(nation,'E',color, 'R'): continue # 条件02 if not check_adj_1(color, 'W',color, 'G'): continue # 条件06 if not check_adj_2(nation,'N',color, 'B'): continue # 条件15 for pet in itertools.permutations(PET): # pet loop if not check_match(nation,'S',pet, 'D'): continue # 条件03 for drink in itertools.permutations(DRINK): # drink loop if not check_match(nation,'U',drink, 'T'): continue # 条件05 if not check_match(color, 'G',drink, 'C'): continue # 条件04 if not check_match(house, '3',drink, 'M'): continue # 条件09 for smoke in itertools.permutations(SMOKE): # tabaco loop if not check_match(smoke, 'O',pet, 'S'): continue # 条件07 if not check_match(color, 'Y',smoke, 'K'): continue # 条件08 if not check_adj_2(smoke, 'C',pet, 'F'): continue # 条件11 if not check_adj_2(pet, 'H',smoke, 'K'): continue # 条件12 if not check_match(smoke, 'L',drink, 'O'): continue # 条件13 if not check_match(nation,'J',smoke, 'P'): continue # 条件14 # チェックを潜り抜けたものだけを表示 print("H: %s"%"".join(house )) print("C: %s"%"".join(color )) print("N: %s"%"".join(nation)) print("D: %s"%"".join(drink )) print("S: %s"%"".join(smoke )) print("P: %s"%"".join(pet )) print(u"∴") print(u"(1)%s人"%Nation[nation[drink.index('W')]]) print(u"(2)%s人"%Nation[nation[pet .index('Z')]]) print('') mkMatTbl((HOUSE,COLOR,NATION,DRINK,SMOKE,PET), \ (HOUSE,color,nation,drink,smoke,pet)) print("Runtime : %.3f [sec]"%(time()-tm)) # Timer Stop & Print if __name__ == '__main__': main()
●実行結果
H: 12345 C: YBRWG N: NUESJ D: WTMOC S: KCOLP P: FHSDZ ∴ (1)N:ノルウェー人 (2)J:日本人 B G R W Y E J N S U C M O T W C K L O P D F H S Z 1 x x x x o x x o x x x x x x o x o x x x x o x x x 2 o x x x x x x x x o x x x o x o x x x x x x o x x 3 x x o x x o x x x x x o x x x x x x o x x x x o x 4 x x x o x x x x o x x x o x x x x o x x o x x x x 5 x o x x x x o x x x o x x x x x x x x o x x x x o D x x x o x x x x o x x x o x x x x o x x F x x x x o x x o x x x x x x o x o x x x H o x x x x x x x x o x x x o x o x x x x S x x o x x o x x x x x o x x x x x x o x Z x o x x x x o x x x o x x x x x x x x o C o x x x x x x x x o x x x o x K x x x x o x x o x x x x x x o L x x x o x x x x o x x x o x x O x x o x x o x x x x x o x x x P x o x x x x o x x x o x x x x C x o x x x x o x x x M x x o x x o x x x x O x x x o x x x x o x T o x x x x x x x x o W x x x x o x x o x x E x x o x x J x o x x x N x x x x o S x x x o x U o x x x x Runtime : 0.187 [sec]
※参考URL
●Zebra Puzzle - Wikipedia
●Pythonで全角文字を含む文字列の幅を取得する - Narrow Escape
●Pythonバージョンの取得方法 - Qiita
●買い物の推理パズルをPythonで解いてみた。(2)
●願い事の推理パズルをPythonで解いてみた。
P.S.
はてなダイアリーから、はてなブログに移行したとき、実行結果の表示が乱れるようになったので、('◯','×')を(' o',' x')に変更しました。
知恵袋で見つけた計算ブロックの問題をPythonで解いてみました。(^_^;
ルール
①図のマスに１から６までの数字を1つずついれます。
②どの列(縦●横とも)にも１から６までの数字が1つずついれます。
③ブロックの中の数字は太線で囲まれたブロックの数の和になります。
0 1 2 3 4 5 +---+---+---+---+---+---+ 0 |13 |16 | + +---+---+---+---+---+ 1 | |3 |11 |7 | +---+---+ + +---+---+ 2 |5 | | |6 |8 | + +---+---+---+ + + 3 | |15 | | | +---+---+---+---+---+---+ 4 |10 |6 |11 | + +---+---+---+---+---+ 5 | |9 |6 | +---+---+---+---+---+---+
ただし、外側の数字は、プログラム用の配列のインデックスです。
● CalcBlocks1.py
# coding: UTF-8 # CalcBlocks1.py from time import time import itertools def toStr(lst): return '[%s]'%','.join(['%s'%x for x in lst]) # 列がダブっていないか調べる def isDuplicated(n,li2D): m = len(li2D) for i in range(m): li = [li2D[j][i] for j in range(n)] if len(set(li))!=n: return True return False def main(): tm = time() # Timer Start m = [[0]*6]*6 R = range(1,7) Perm = [list(itertools.permutations(R))]*5 for m[0] in Perm[0]: if m[0][1]+m[0][2]+m[0][3]+m[0][4]+m[0][5]!=16: continue for m[1] in Perm[1]: if m[0][0]+m[1][0]+m[1][1]!=13: continue if m[1][4]+m[1][5]!=7: continue if isDuplicated(2,m): continue for m[2] in Perm[2]: if m[1][2]+m[2][2]!= 3: continue if m[1][3]+m[2][3]!=11: continue if isDuplicated(3,m): continue for m[3] in Perm[3]: if m[2][0]+m[2][1]+m[3][0]!= 5: continue if m[3][1]+m[3][2]+m[3][3]!=15: continue if m[2][4]+m[3][4]!= 6: continue if m[2][5]+m[3][5]!= 8: continue if isDuplicated(4,m): continue for m[4] in Perm[4]: if m[4][1]+m[4][2]+m[4][3]!= 6: continue if m[4][4]+m[4][5]!=11: continue if isDuplicated(5,m): continue for i in range(6): li = [m[j][i] for j in range(5)] m[5][i] = 21-sum(li) if m[4][0]+m[5][0]!=10: continue if m[5][1]+m[5][2]!= 9: continue if m[5][3]+m[5][4]+m[5][5]!= 6: continue # チェックを潜り抜けたものだけを表示 for n in range(6): print(toStr(m[n])) print("Runtime : %.3f [sec]"%(time()-tm)) # Timer Stop & Disp if __name__ == '__main__': main()
●実行結果
[5,3,4,2,6,1] [2,6,1,5,3,4] [3,1,2,6,4,5] [1,5,6,4,2,3] [4,2,3,1,5,6] [6,4,5,3,1,2] Runtime : 0.625 [sec]
※参考URL
●判断推理のダンスのペアの問題をPythonで解いてみた。
●計算ブロックの問題をPythonで解いてみた。(2)
