9 * 9 Sudoku Solver
こんにちは。 今日は 9 * 9 の数独（ナンバープレイス）を Python に解かせてみました。
実は以前にも数独解くプログラムを作っていて、ごく簡単な問題は解けたのですが難しい問題は溶けていませんでした。 ところが先日蟻本を読んでいたら、「あれ？深さ優先探索でいけんじゃね？」と思い立ち（というか蟻本の探索の項に数独に使える的な記述があるw）、書いてみました。
ソースコード
# -*- coding: utf-8 -*-
def main():
print ''
print '空欄を0として1行ずつ問題を入力してください。'
problem = getProblem()
if validProblem(problem):
if solve(0, 0, problem):
print '解けた！'
else:
print '解けなかった…orz'
for y in range(0, 9):
for x in range(0, 9):
print problem[y][x],
print
else:
print '不正な問題です。もう１度最初から入力しなおしますか？ (yes/no)'
if raw_input() == 'yes':
main()
def getProblem():
problem = []
for y in range(0, 9):
input = raw_input('...')
while len(input) != 9 or not input.isdigit():
print '不正な入力です。もう１度同じ行を入力してください。'
input = raw_input('...')
problem.append([int(n) for n in input])
return problem
def validProblem(problem):
for y in range(0, 9):
for x in range(0, 9):
if problem[y][x] != 0:
if not isValid(x, y, problem):
return False
return True
def solve(x, y, workspace):
if (x, y) == (0, 9):
return True
if workspace[y][x] == 0:
for n in range(1, 10):
workspace[y][x] = n
if isValid(x, y, workspace):
(nx, ny) = nextPoint(x, y)
if solve(nx, ny, workspace):
return True
workspace[y][x] = 0
return False
else:
(nx, ny) = nextPoint(x, y)
if solve(nx, ny, workspace):
return True
def isValid(x, y, workspace):
for yoko in range(0, 9): # 横を見る
if x != yoko:
if workspace[y][x] == workspace[y][yoko]:
return False
for tate in range(0, 9): # 縦を見る
if y != tate:
if workspace[y][x] == workspace[tate][x]:
return False
for gy in range(y/3*3, (y/3+1)*3): # 3*3グループを見る
for gx in range(x/3*3, (x/3+1)*3):
if (y,x) != (gy, gx):
if workspace[y][x] == workspace[gy][gx]:
return False
return True
def nextPoint(x, y):
x += 1
if x > 8:
x = 0
y += 1
return (x, y)
if __name__ == '__main__':
print '9 * 9 Sudoku Solver by yosida95'
main()
これを実行すると問題を訊かれるので指示通りに問題を入力すると解いてくれます。
解が2つ以上あったり、理論だけでなく勘に頼るような問題（本来それは数独の問題として成立していない）でも、すべての組み合わせを試しますので、解けると思います。 ただし、解が2つ以上の問題はそのうち最初に見つかった解1つの出力です。
試しに以前 GIGAZINE で紹介されていた世界一難しい数独を解かせたときのスクリーンショットがこちら。 （コンピューターに解かせた結果も写っていますのでご注意ください）
なお、プログラムの作成に当たっては当初「 Pythonで数独ソルバーを実装した | 日曜研究室」を参考にさせていただいていました。 そのため、影響を強くうけている部分があります。 書きあがった後で比較したら solve 関数なんかまんまな気がします。
