日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問９６「数独」
"数独"(日本語で数字を配置するという意味)とは人気があるパズルの名前である.
起源は不明だが, その評判はラテン語で"Squares"と呼ばれる同様な,
そしてはるかに難しいパズルを考案したレオンハルト・オイラーの貢献によるものに違いない.
しかしながら, "数独"パズルの目的はそれぞれの行, 列が3×3の枠を含む9×9の格子の空白（もしくは0）をそれぞれ1から9の数字で置き換えることである.
下に, 一般的なパズルの開始状態とその解答の例がある.
うまく作られている"数独"パズルは, 選択肢を消去するために"仮定とテスト"方式を用いる必要があるかもしれないが, ただ一つの解を持ち, 論理によって解くことができる(これについては様々な意見がある).
探索の複雑さがパズルの難易度を決定する; 上に挙げた例は, 単純で直接的な推論によって解く事ができるため, 簡単であると考えられる.
6kバイトのテキストファイルsudoku.txt(右クリックで,"名前をつけてリンク先を保存") にはただ一つの解を持つ, 様々な難易度の50の"数独"パズルが含まれている(上の例題はこのファイルにおける最初のパズルである).
50すべてのパズルを解き, それぞれの解答の左上隅にある3桁の数の合計が求めよ;
例えば483は上の解答例の左上隅の3桁の数である.
注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。
私の回答例は以下の通りです。
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
0 件のコメント:
コメントを投稿