Sudoku Solver (Incinerator) - 数独（ナンプレ）
Incinerator最後の問題。
どんな問題？
Sudoku Solver
http://www.checkio.org/mission/sudokusolver/
数独を解け。
数独（ナンプレ）は、縦の9マス、横の9マス、サブグリッド(3x3)に1～9の数字を重複しないように配置していくパズル。有名だけど、あまりやったことないなぁ。お絵かきロジック（ピクロス）は好きなんだけど。
引数は、数独の問題をlist of listで渡される。0が空欄となる。サイズは9x9の固定。
戻り値は、0（空欄）をすべて1～9で埋めた状態で返せばよい。
例題：
checkio([[5, 0, 0, 7, 1, 9, 0, 0, 4], [0, 0, 1, 0, 3, 0, 5, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 8, 5, 9, 7, 2, 6, 4, 0], [0, 0, 0, 6, 0, 1, 0, 0, 0], [0, 2, 6, 3, 8, 5, 9, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 3, 0, 5, 0, 2, 0, 0], [8, 0, 0, 4, 9, 7, 0, 0, 6]]) == [[5, 6, 8, 7, 1, 9, 3, 2, 4], [9, 7, 1, 2, 3, 4, 5, 6, 8], [2, 3, 4, 5, 6, 8, 7, 9, 1], [1, 8, 5, 9, 7, 2, 6, 4, 3], [3, 9, 7, 6, 4, 1, 8, 5, 2], [4, 2, 6, 3, 8, 5, 9, 1, 7], [6, 1, 9, 8, 2, 3, 4, 7, 5], [7, 4, 3, 1, 5, 6, 2, 8, 9], [8, 5, 2, 4, 9, 7, 1, 3, 6]]
どうやって解く？
各マスごとに、数字の候補を絞っていけばいいだろう。例えば、上の例題なら、(x,y)=(1,0)のマスは、
- 横の並びが [5,0,0,7,1,9,0,0,4] だから、{5,7,1,9,4}以外の数字。
- 縦の並びが [0,0,0,8,0,2,0,0,0] だから、{8,2}以外の数字。
- サブグリッドが [5,0,0],[0,0,1],[0,0,0] だから、{5,1}以外の数字。
ということがわかる。つまり{3,6}のどちらかとなる。
このようにすべてのマスを調べて、1つの数字が残るマスがあればそのマスは確定。
これを繰り返せば解けるはずだ。
import itertools def checkio(grid): def get_value(x, y): return grid[y][x] def set_value(pt, value): grid[pt[1]][pt[0]] = value def cells(): return [(x, y) for y in range(9) for x in range(9)] def get_horizontal_numbers(pt): # 横の数字列 return [get_value(x, pt[1]) for x in range(9)] def get_vertical_numbers(pt): # 縦の数字列 return [get_value(pt[0], y) for y in range(9)] def get_sub_grid_numbers(pt): # サブグリッドの数字列 sx, sy = pt[0] // 3 * 3, pt[1] // 3 * 3 return [get_value(sx + x, sy + y) for y in range(3) for x in range(3)] while any([e == 0 for row in grid for e in row]): # ボードから0がなくなるまで繰り返す for pt in cells(): if get_value(*pt) == 0: numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9} numbers -= set(get_horizontal_numbers(pt)) numbers -= set(get_vertical_numbers(pt)) numbers -= set(get_sub_grid_numbers(pt)) if len(numbers) == 1: set_value(pt, numbers.pop()) show_grid(grid) return grid
…これではダメだった。
途中まではいけるが、数字が1つに絞れないケースが出てくるとwhileを抜けられない。
まず、デバッグ用にgridを表示する関数を作成した。
def show_grid(grid): for y in range(9): print(''.join('０１２３４５６７８９'[i] for i in grid[y]))
セルフチェックの1問目で確認する。
０７１６８４０００ ０４９７０００００ ５００００００００ ０８００００５０４ ０００３０７０００ ２０３００００９０ ００００００００９ ０００００３７２０ ０００４９８６１０
これを解いていくと、
３７１６８４９５２ ０４９７０００００ ５００００００００ ０８００００５０４ ０００３０７０００ ２０３００００９０ ００００００００９ ０００００３７２０ ７００４９８６１０
ここまで進んで止まる。
ちょっと自力で解いてみよう。
…
…あれ？全然わからない。これ以上はどうやって進めるの？？？
しかたない、Wikipedia先生！
数独の解法
- 一つのマスに注目して、そのマスに入る数字を限定する。
- 一つの列（または3×3のブロック）に注目して、特定の数字が入るマスを探す。
- ある数字が入る場所が、単一ブロックの同一列に限定されるとき、他のブロックのその列には入らない。
- n個の数字がn個のマスに入ることが限定されるとき、他の数字はそれらのマスに入らない。
私のコードは1しか対応してなかった。
2は、例えば「×」のマスに数字の5が入らないことが分かれば、「？」のマスが５だと確定する。
| × | × | × |
| × | × | × |
| ？ | × | × |
2のパターンを追加する
まずは、先ほどのコードに2のパターンを追加した。
def checkio(grid): (略) def get_sub_grid_pts(pt): sx, sy = pt[0] // 3 * 3, pt[1] // 3 * 3 return {(sx + x, sy + y) for y in range(3) for x in range(3)} def sub_grid_origins(): return [(x * 3, y * 3) for y in range(3) for x in range(3)] def same_sub_grid(pt1, pt2): return pt1[0] // 3 == pt2[0] // 3 and pt1[1] // 3 == pt2[1] // 3 while any([e == 0 for row in grid for e in row]): for pt in cells(): if get_value(*pt) == 0: numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9} numbers -= set(get_horizontal_numbers(pt)) numbers -= set(get_vertical_numbers(pt)) numbers -= set(get_sub_grid_numbers(pt)) if len(numbers) == 1: set_value(pt, numbers.pop()) for n in range(1, 10): # フラグを作成（nになりえる空きマスはTrue） flags = {pt: get_value(*pt) == 0 for pt in cells()} # 数字nと同じ列、同じサブグリッドをFalseにする for pt in cells(): if get_value(*pt) == n: for p in cells(): if p[0] == pt[0] or p[1] == pt[1] or same_sub_grid(pt, p): flags[p] = False # サブグリッド内でTrueが一つだけなら確定 for origin in sub_grid_origins(): pts = [p for p in get_sub_grid_pts(origin) if flags[p]] if len(pts) == 1: print('[2]', pts[0], n) set_value(pts[0], n) return grid
この結果がこちら。
３７１６８４９５２ ０４９７０００００ ５０００００４７０ ０８７０００５３４ ０００３０７２００ ２０３８００１９７ ００００７００４９ ０００００３７２０ ７００４９８６１０
先ほどよりは、少し進んだが、やはり解けない。
やはり、3,4のパターンに対応させなくては解けないのだろう。
3.ある数字が入る場所が、単一ブロックの同一列に限定されるとき、他のブロックのその列には入らない。
サブグリッドの中の1列（3マス）に注目して、残りの2列には含まれない数字があれば、他のブロックの同じ列から、その数字の候補を除外できる…
なんかややこしくなってきたなぁ。
まず、サブグリッドを3マスと6マスに分割する。分割方法は縦と横で6通り。それぞれについて、他のブロックの同じ列を求めて…
…
はぁー、なんか煮詰まってきた（泣）
明日にしようかな
なんか昨日のアナグラムの問題でも、すごく煮詰まってて、でもBFSであっさり解けたんだっけ…。
ひょっとして
あれ、この問題も探索と考えればいいのかも。
迷路の探索と比較してみよう。
- 上下左右への移動は、空きマスに何か数字を入れること。
- 障害物は、数字を入れると矛盾するような状態。
- スタートは、初期のボードの状態。
- 現在位置は、現在のボードの状態。
- ゴールは、ボードの空きマスが全部埋まった状態。
あれ、いけそうだな。空きマスを1つ埋めることが1歩進むみたいなイメージか。そもそも今回は、空きマスの数が決まってるんだから、最短経路なんて無い。だったらDFSでいいのか。
import copy def checkio(grid): def get(x, y): return data[y][x] def get_possible_numbers(x, y): # (x,y)のマスに置くことのできる数字を探す result = {1, 2, 3, 4, 5, 6, 7, 8, 9} for yy in range(9): result -= {get(x, yy)} for xx in range(9): result -= {get(xx, y)} for gy in range(3): for gx in range(3): xx = x // 3 * 3 + gx yy = y // 3 * 3 + gy result -= {get(xx, yy)} return result q = [grid] while len(q) > 0: data = q.pop() # DFSなのでキューではなくスタック # 空きマスを取得 empty_cells = [(x, y) for y in range(9) for x in range(9) if get(x, y) == 0] if len(empty_cells) == 0: return data # 空きマスの一つに数字を入れる x, y = empty_cells[0] for num in get_possible_numbers(x, y): new_data = copy.deepcopy(data) new_data[y][x] = num q.append(new_data)
list of list をコピーするために、copy.deepcopy()を使っている。
ちょっと時間はかかったが、あっさりとクリア。
なんだよ、おまえもか。人間が解いていく過程をコード化しようと試行錯誤してたのに、そんなものより総当たりでやればあっさり解けるなんて、なんかちょっと…
まとめ
気を取り直して。
さっきのコードでは、ボードの状態をlist of listのままでスタックに保存していた。これだと、deepcopyが必要だし、処理も時間がかかるので、一旦、listに変換し、最後にlist of listに直すように修正した。これで体感的にもだいぶ速くなった。
def checkio(grid): def get(x, y): return data[y * 9 + x] def get_possible_numbers(index): x, y = index % 9, index // 9 result = {1, 2, 3, 4, 5, 6, 7, 8, 9} for yy in range(9): # col result -= {get(x, yy)} for xx in range(9): # row result -= {get(xx, y)} for gy in range(3): # sub grid for gx in range(3): result -= {get(x // 3 * 3 + gx, y // 3 * 3 + gy)} return result q = [[e for row in grid for e in row]] # list of list -> list while len(q) > 0: data = q.pop() # DFS zero_cells = [i for i in range(81) if data[i] == 0] if len(zero_cells) == 0: return [data[i:i + 9] for i in range(0, len(data), 9)] # list -> list of list cell_index = zero_cells[0] for num in get_possible_numbers(cell_index): new_data = data[:] # data.copy() new_data[cell_index] = num q.append(new_data)
よし、これで公開。
まあ、余裕があれば、Wikipediaに載っていた1～4の解法をそのままコード化したいところだけど、もう疲れたので、またいずれ。
何はともあれ、これでIncineratorをコンプリート！！！終盤は難問続きで苦労した。
次はMine、と言いたいところだが難しそうなので、簡単そうな Library 2.0 に行くことにする。
