Sunday, April 13, 2014

数独再び

以前の数独を解くプログラムを書いたが、お粗末だった印象がありました。
この前、とある飲み会で数独の話が出て、数独を制約の問題としてとらえるという話を聞きました。ネットで調べてみると、Sugarを使って解いている人がいる。Sugarなら自分のパソコンにも入っているので試してみようかという気になったけれど、ちょっと味気ないかな。
まずは普通のやり方をやり直してみようと思いました。

数独の問題は9x9のマスにところどころ数字が入っていて、穴埋めをする。ルールは縦横と、その穴が属する3x3の領域のいずれもそれぞれ異なる数字(1から9)を入れる。

問題のテキストは穴のところにに0が書かれているものとして、0の代わりに数字を入れて答えるものとしよう。解き方の手順はこうだ。

まず0のところを探す。もう0がなければ完成、現在の盤が答え。0を見つけたら縦横と3x3の箱を見渡して、使われている数字をリストアップする。そこから候補となる数字のリストを得る。

候補の数字を一個使って、新しい盤を作る。次の0を探す。これを順番に繰り返す。候補が無ければ失敗。

答えが複数ある場合も気になるけれど、とりあえず答えは一個しかないものとして良いだろう。

盤は行列の形で扱っても良いが、一本のベクトルだと思っても良いだろう、ということで後者にした。以下、pythonで書いたソルバー。なかなかシンプルに書けたと思うんだけど。


def cand(bd, pos):
  px, py = pos/9, pos%9
  i,j = (px/3)*3, (py/3)*3
  s = set([bd[9*x+py] for x in xrange(9)]+[bd[9*px+y] for y in xrange(9)]+ 
          [bd[9*x+y] for x in xrange(i,i+3) for y in xrange(j,j+3)])
  return list(set(range(10))-s)

def solver(b, pos):
  for p in xrange(pos, 81):
    if b[p] == 0:
      for c in cand(b, p):
        r = solver(b[:p]+[c]+b[p+1:],p+1)
        if r: return r
      return []
  return b

呼び出すときはまあこんな風に。

solver([0,0,3,0,2,0,6,0,0,9,0,0,3,0,5,0,0,1,0,0,1,8,0,6,4,0,0,0,0,8,1,0,2,9,0,0,7,0,0,0,0,0,0,0,8,0,0,6,7,0,8,2,0,0,0,0,2,6,0,9,5,0,0,8,0,0,2,0,3,0,0,9,0,0,5,0,1,0,3,0,0],0)

Haskellでも同じプログラムを書いたので貼付けてみようと思ったのだけど、なんだかうまく行かないんですよね。Haskellでよく使う半角の<ーという記号がダメっぽい。


No comments: