def d0(d):
for x,y in Lxy():
if not d[x,y]: d[x,y] = list(xrange(1,10))
return d
def d1(d):
for x,y in Lt(d):
d[x, y] = sorted(set(d[x, y])-set(Ka(d,x,y)))
return d
def d2(d):
for x,y in Lt(d):
for L in [Ltx(d,y), Lty(d,x), Ltm(d,x,y)]:
M = [s for i,j in L for s in d[i,j]]
N = [s for s in d[x,y] if M.count(s)==1]
if N: d[x,y] = N
return d
def d3(d):
for n in xrange(1, 10):
setn = set([n])
for x,y in Lm3():
N = [(i,j) for i,j in Ltm(d,x,y) if (n in d[i,j])]
if len(N)!=2: continue
if N[0][0]==N[1][0]:
for i,j in Lty(d, N[0][0]):
if (i,j) not in N: d[i,j] = sorted(set(d[i,j])-setn)
if N[0][1]==N[1][1]:
for i,j in Ltx(d, N[0][1]):
if (i,j) not in N: d[i,j] = sorted(set(d[i,j])-setn)
return d
def d4(d):
for n in xrange(1, 10):
setn = set([n])
for s in xrange(9):
L = [j for i,j in Lty(d,s) if (n in d[i,j])]
if len(L)!=2: continue
for i in sorted(set(xrange(9))-set([s])):
N = [j for i,j in Lty(d,i) if (n in d[i,j])]
if len(N)!=2: continue
if sorted(L)!=sorted(N): continue
for j in L:
for k,j in Ltx(d,j):
if k not in [s,i]: d[k,j] = sorted(set(d[k,j])-setn)
for s in xrange(9):
L = [i for i,j in Ltx(d,s) if (n in d[i,j])]
if len(L)!=2: continue
for j in sorted(set(xrange(9))-set([s])):
N = [i for i,j in Ltx(d,j) if (n in d[i,j])]
if len(N)!=2: continue
if sorted(L)!=sorted(N): continue
for i in L:
for i,k in Lty(d,i):
if k not in [s, j]: d[i,k] = sorted(set(d[i,k])-setn)
return d
def d5(d):
for x in xrange(9): d = f5(d, Lty(d, x), Vty(d, x))
for y in xrange(9): d = f5(d, Ltx(d, y), Vtx(d, y))
for x,y in Lm3(): d = f5(d, Ltm(d, x, y), Vtm(d, x, y))
return d
def f5(d, Li, Lv):
L = [s for s in Lv if len(s)==2]
M = sorted(set([tuple(s) for s in L if Lv.count(s)==2]))
M = [list(s) for s in M]
for L in M:
for n in L:
setn = set([n])
for i, j in Li:
if d[i, j]!=L: d[i, j] = sorted(set(d[i, j])-setn)
return d
def Lxy(): return [(x, y) for x in xrange(9) for y in xrange(9)]
def Lm(x, y): return [(x//3*3+i, y//3*3+j) for j in xrange(3) for i in xrange(3)]
def Lm3(): return [(x, y) for x in xrange(0,9,3) for y in xrange(0,9,3)]
def Lt(d): return [(x, y) for x,y in Lxy() if isinstance(d[x,y], list)]
def Ltx(d,y): return [(x, y) for x in xrange(9) if isinstance(d[x,y], list)]
def Lty(d,x): return [(x, y) for y in xrange(9) if isinstance(d[x,y], list)]
def Ltm(d,x,y): return [(x, y) for x, y in Lm(x,y) if isinstance(d[x,y], list)]
def Vx(d, y): return [d[x, y] for x in xrange(9)]
def Vy(d, x): return [d[x, y] for y in xrange(9)]
def Vm(d, x, y): return [d[x, y] for x,y in Lm(x, y)]
def Va(d, x, y): return Vx(d, y)+Vy(d, x)+Vm(d, x, y)
def Vtx(d, y): return [s for s in Vx(d, y) if isinstance(s, list)]
def Vty(d, x): return [s for s in Vy(d, x) if isinstance(s, list)]
def Vtm(d, x, y): return [s for s in Vm(d, x, y) if isinstance(s, list)]
def Kx(d, y): return [s for s in Vx(d, y) if isinstance(s, int)]
def Ky(d, x): return [s for s in Vy(d, x) if isinstance(s, int)]
def Km(d, x, y): return [s for s in Vm(d, x, y) if isinstance(s, int)]
def Ka(d, x, y): return sorted(set(Kx(d, y)+Ky(d, x)+Km(d, x, y)))
def chk(d):
N = list(xrange(1, 10))
for i in xrange(9):
if sorted(Vx(d,i))!=N: return False
if sorted(Vy(d,i))!=N: return False
for x,y in Lm3():
if sorted(Vm(d,x,y))!=N: return False
return True
def f(sIn):
pIn = open(sIn)
L = pIn.read().split("\n")
c = 0
for i in xrange(0, len(L), 10):
print "-------\n",L[i]
d = {}
for x,y in Lxy(): d[x,y] = int(L[i+y+1][x])
d = d0(d)
while not chk(d):
dd = d.copy()
for i in xrange(1, 6):
for x, y in Lt(d):
if len(d[x,y])==1: d[x,y] = d[x,y][0]
d = eval("d"+str(i)+"(d)")
if dd!=d: break
for y in xrange(9): print y,[d[(x,y)] for x in xrange(9)]
c += d[0,0]*100+d[1,0]*10+d[2,0]
pIn.close()
pIn = None
return c
if __name__=="__main__":
import os, sys
sIn = os.path.join(os.path.dirname(__file__), "problem096_sudoku.txt")
s = f(sIn)
print s
数独を辞書dに格納します。
辞書dのキーは(0,0)-(8,8)の81マスの位置を示す座標タプルで、
値は候補値の配列（リスト型）、または確定値（整数型）です。
１．関数f(sIn)
・問題ファイルのパスを受け取り、リストLに各行を要素として全部読み込みます。
・リストLをヘッダを含めた10行ごとに取り出し、
左上(0,0)-右下(8,8)の81マスの位置を示す座標タプルをキーとする辞書d
に、値を１つずつ格納しておきます。
・最初に関数d0()で未設定値0を候補リストまたは確定値に変換しておきます。
・次に、関数chk()で数独辞書dが完成したかチェックOKになるまで、関数d1()から関数d5()を順に行います。
ただし、関数d1()から関数d5()はこの順に基本的な操作から順に並べているので、マスの値が１つでも変化した時点で、改めて関数d1()から再処理します。
・数独が完成したら、左上３マスの値を３桁の数値にして、変数cに累積します。
２．関数d0():
・数独辞書dの未設定値0のマスに[1～9]を候補リストとして設定します。
３．関数d1()
・数独全体の候補リストについて、候補リストから関係項目に存在する確定値を削除します。
４．関数d2()
・行内、列内、3x3メッシュ内もそれぞれで、その全候補値の中に１つだけ存在する値があれば確定値とします。
５．関数d3()
・3x3メッシュ内に２つだけある候補値の位置が一列に並んでいるとき、
どちらかが確定値（例の○か◎）なので、
その並んでいる行内、または列内の他の候補からその値（例の×）を削除します。
６．関数d4()
・ある候補値が２つだけ存在する行が２つあり、しかもその列位置が同じ場合、
これら４つの値のうち、いずれかの対角位置の候補値が確定値（例の○か◎）になるため、この２つの列内の候補リストから、この候補値（例の×）を削除します。
列についても上記と同様に処理します。
７．関数d5()
・行内に、候補値が２つだけの同一の候補リストが２つのマスにある場合、
どちらの候補値もどちらかのマスのそれぞれの確定値（下図の○か◎）になるため、このマスを含む、列内、また3x3メッシュがあればそれも含めた候補リストからこの２つの値（例の×）を削除します。
列内も同様です。
８．その他
部品となる関数を以下の通りです。
・Lxy():全マスの項目番号リスト
・Lm(x, y)：数独辞書dのx列y行が含まれる3x3メッシュの項目番号リスト
・Lm3() ：3x3メッシュの左上マスの項目番号リスト
・Lt(d) ：数独辞書dの処理中の項目番号リスト
・Ltx(d,y)：数独辞書dのy行目の処理中の項目番号リスト（横方向）
・Lty(d,x) ：独辞書dのx列目の処理中の項目番号リスト（縦方向）
・Ltm(d,x,y)：数独辞書dのx列y行が含まれる3x3メッシュの処理中の項目番号リスト
・Vx(d, y) ：数独辞書dのy行目の値リスト（横方向）
・Vy(d, x) ：数独辞書dのx列目の値リスト（縦方向）
・Vm(d, x, y)：数独辞書dのx列y行目が含まれる3x3メッシュの値リスト
・Va(d, x, y)：数独辞書dのx列y行に関係する値リスト
・Vtx(d, y) ：数独辞書dのy行目の値リスト（横方向）
・Vty(d, x) ：数独辞書dのx列目の値リスト（縦方向）
・Vtm(d, x, y)：数独辞書dのx列y行目が含まれる3x3メッシュの値リスト
・Kx(d, y) ：数独辞書dのy行目の確定値リスト（横方向）
・Ky(d, x) ：数独辞書dのx列目の確定値リスト（縦方向）
・Km(d, x, y)：数独辞書dのx列y行目が含まれる3x3メッシュの確定値リスト
・Ka(d, x, y)：数独辞書dのx列y行に関係する確定値リスト
・chk(d):#数独辞書dの縦、横、3x3メッシュの全てが[1～9]であるかの最終チェック
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
24702
