最近、心持ちに余裕ができてきたのと、仕事でプログラムを書いていることがあり、さらに、知り合いが数独をやっているというのを聞いたので、なんとなく書いてみた。

rubyでやってみたら案外あっさりできて、入出力は最低限にして、解く部分だけで80行くらい。

工夫した点は、いきなり上から数字を全通り試さずに、
１．自明なマスはすべて埋めてから。
２．2択になっているところから順に総当たり。
という点。

総当たりで、解けなかったら置いたところまで戻る、、というのはやっぱり再帰で書くのが簡単なので、そうした。

#!/usr/bin/env ruby
require 'yaml'
Q=YAML.load_file("quiz.yaml")

class Sudoku 
  def initialize(a=Q[0],flag_one=true)
    @quiz=a.map{|arr|arr.freeze}.freeze
    @ans=copy(@quiz)
    @flag_one=flag_one
    @store=[]
    self.solve
  end
  def solve
    rec unless solved?
    @store
  rescue => err
    p err,@ans
  end
  def solved?
    (0..8).each{|i|(0..8).each{|j|
        return false if @ans[i][j]==0
      }}
    return true
  end
  private
  # 行、列からブロックへ変換。逆変換も同じ。
  def ij2kl(i,j)
    k=j/3 + (i/3)*3
    l=j%3 + (i%3)*3
    return k,l
  end
  # メインの再帰関数。
  def rec(i=0,j=-1, thr=0)
    while true
      raise "unsolvable!" if thr > 9
      if j==8
        thr+=1 if i==8
        i=(i+1)%9
      end
      j=(j+1)%9
      next unless @ans[i][j]==0

      # ここからi,jマスの処理。
      arr=hantei(i,j) 
      case arr.length
      when 0 then # 解けない！
        return nil
      when 1 then
        @ans[i][j]=arr[0]
        if solved?
          p "solved!",@ans
          @store.push(copy(@ans))
          return true
        else
          thr = 0
        end
      # 候補が複数残ったところから再帰。
      when 2..thr then
        wk=copy(@ans)
        arr.each{|v|
          @ans[i][j]=v
          rec(i,j)
          return nil if @flag_one && solved?
          @ans=copy(wk)
        }
        break # 仮定したところを全部試したら無限ループを抜ける。
      end
    end
  end
  # i,j マスが決まるかどうかを判定
  def hantei(i,j)
    k,l=ij2kl(i,j)
    tmp = @ans[i][0..8]
    (0..8).each{|ii|
      ki,kj=ij2kl(k,ii)
      tmp << @ans[ii][j]
      tmp << @ans[ki][kj]
    }
    [1,2,3,4,5,6,7,8,9] - tmp.uniq
  end
  def copy(a)
    Marshal.load(Marshal.dump(a))
  end
end
Sudoku.new(Q[0])

http://apollon.issp.u-tokyo.ac.jp/~watanabe/sample/sudoku/index_j.html
ここで公開されている数独を食わせてみたら、ちょっと止めたくなるくらい時間がかかったので、いろいろと小細工してみたけども、かえって遅くなるばかりだった。。。

次は練習に、pythonとかocamlとかで書いてみようかな。