BLOG

将来の夢はおもしろお兄さんです。

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 '不正な問題です。もう1度最初から入力しなおしますか? (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 '不正な入力です。もう1度同じ行を入力してください。'
      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 で紹介されていた世界一難しい数独を解かせたときのスクリーンショットがこちら。 (コンピューターに解かせた結果も写っていますのでご注意ください)

answer

なお、プログラムの作成に当たっては当初「 Pythonで数独ソルバーを実装した | 日曜研究室」を参考にさせていただいていました。 そのため、影響を強くうけている部分があります。 書きあがった後で比較したら solve 関数なんかまんまな気がします。