#! ruby 

#                   数独
#
# :call-seq:
#   ruby sudoku.rb .  --> STDOUT
#     ピリオドが指定された場合$dataListに指定された初期データを解く
#   
#   ruby sudoku.rb <fileName>  --> STDOUT
#     ファイル名が指定された場合、初期データをファイルから読んで解く
#     データは空白またはカンマ','で区切られた一桁の数値が９個並んだ行とする。
#     その他の行は無視される。行中の'|'は空白とみなされる。
#   
#   ruby sudoku.rb make <n> --> STDOUT
#     <n>は十進数の数値。
#     <n>で指定された個数の問題を作る。
#     小文字のmakeで指定した場合、解答を出さない。
#     大文字のMAKEで指定した場合、解答も出す。
#     <n>を指定しない場合には１個とする。
#
#   その他の場合、標準入力からデータを受け取って解答する。
#     データ形式はファイルと同じとする。
#     パイプで自身の出力を受けることも出来る。
#
#   先頭の引数が -path なら解答手順(推論手順)を出力する。
#   *付で表示される物はその時点で確定されては居ないが単独の数値の可能性しか
#   無くなっているセルを現す。*無しの物がこのプログラムが確定したセルとして
#   取り扱った記録となる。
#
#
#   Ver. 1.00 2006/04/03 : Designed by Mt.Trail 
#   Ver. 2.00 2006/10/20 : Mt.Trail , add Make-mode
#   Ver. 2.01 2006/10/21 : Mt.Trail , bug fix
#   Ver. 2.02 2006/10/21 : Mt.Trail , add Limit of space area
#   Ver. 3.00 2006/10/22 : Mt.Trail , Remake
#   Ver. 3.01 2006/10/24 : Mt.Trail , change Make-Algorithm (Blocked-cell first)
#   Ver. 3.02 2006/10/24 : Mt.Trail , add solved-path output option
#   Ver. 3.03 2006/11/01 : Mt.Trail , change, cell-relations are created by Table, not Cell#   Ver. 3.04 2006/11/04 : Mt.Trail , add ignore character '[',']'
#
# -Memo-
#   2006/11/01 ver. 3.03
#   Ver3.03での変更は、表の形が単一の9x9から、重なり合ったテーブルでも同じ様に
#   処理できるようにするための変更。
#   Tableクラスを変更して初期化部分と結果出力部分を作り変えれば、
#   Cellはそのままでも複雑に重なった構造の表も実現可能。
#   
$rcs = "$Revision: 1.2 $ $Date: 2006/11/04 09:31:46 $"
$KCODE = "s"

# $BlankLimitは空白項の最低数制限、
# この数以上の空欄を持つ解を探すので大きくするとリトライ数が増える。
# 0 <= $BlankLimit < (81-17=64)
$BlankLimit = 45

# Debug control flag
#$debugMode = true
$debugMode = false

# Debug control for solve-function
#$debugModeS = true
$debugModeS = false


# 初期値用コード出力フラグ
$initial_dataout = false

# 問題作成時に解答も出力するか
$solved_ans = false

# 問題作成時に手順も出力するか
$solved_path_on = false

# 解答探索時に最後まで確定しなかったセルのうちのひとつのセルの情報
$solveHint = []


#
# 初期データ
#   空欄部分は0で指定する
#
$data1 = [
    [0,0,4,  0,5,0,  0,1,0],
    [6,0,0,  2,0,0,  5,0,0],
    [0,3,0,  0,0,7,  0,0,9],

    [0,0,5,  0,3,0,  0,8,0],
    [7,0,0,  6,0,8,  0,0,4],
    [0,4,0,  0,7,0,  3,0,0],

    [8,0,0,  5,0,0,  0,9,0],
    [0,0,6,  0,0,4,  0,0,8],
    [0,2,0,  0,6,0,  7,0,0] 
]

# ---------------------------------

#
#  初期値のリスト、指定されたものを解く
#
$dataList = [$data1]


# ==========================================================

#
# 表の「１セル」を現すクラス
#
class DokuCell

  # @numberは可能性のある数値要素の文字列
  attr_accessor :number
  
  # @fixedはこのセルの数値要素が確定されたときにTRUEとなる
  attr_accessor :fixed


  ## ------------------------------------------
  ## ----  Initialize Cell Data ---------------
  ## ------------------------------------------
  #
  # セルの初期化
  #   位置(x,y)と数値nを受け取り初期化する
  #   nがゼロの場合には空欄指定とし、1-9を可能性のある数値とする
  #
  def initialize(x,y,n,table)
    @fixed = false      # 確定フラグ true=確定、false=未確定
    @memberH = []       # 水平(x)方向の関連セルのリスト
    @memberV = []       # 垂直(y)方向の関連セルのリスト
    @memberB = []       # 3x3ブロックの関連セルのリスト
    @number = ""        # 可能性のある数値の文字列 '1'-'9'で構成される
    @x = x              # x 位置
    @y = y              # y 位置
  @table = table      # 所属する表

    # 初期値が０の場合には空欄なので1-9の可能性あり、その他の場合には指定値を初期値とする
    @number = (n == 0) ? "123456789" : "#{n}"

    # 表の未確定セルに自分を登録。
    @table.notFixedMembers.push([x,y])

  end

  # m = [x,y] をメンバーに追加する
  def add_H_member(m)
    @memberH.push(m)
  end
  

  # m = [x,y] をメンバーに追加する
  def add_V_member(m)
    @memberV.push(m)
  end
  

  # m = [x,y] をメンバーに追加する
  def add_B_member(m)
    @memberB.push(m)
  end
  
  ## ------------------------------------------
  ## ----  Delete fixed number and the member -
  ## ------------------------------------------
  #
  # (x,y)で指定されたセルがnに確定された通知を受け取る。
  #
  # 既に自分が確定していれば以下の処理はしない。
  # 確定されたnを自分の可能性リストから外す。
  # 自分の候補がひとつになったら表のunoMembersに登録する。
  # typeで指定された関連セルから確定したセルを外す。
  #
  def notice_from_fixed_cell(x,y, n, type)

    # デバッグ用パラメータチェック
    if $debugMode
      er = ""
      er += "x < 1 "          if x < 0
      er += "x > 8 "          if x > 8
      er += "y < 1 "          if y < 0
      er += "y > 8 "          if y > 8
      er += "n is #{n.type} " if ! n.kind_of?(String)
      er += "n=#{n} "         if n.size != 1
      er += "type=#{type} "   if (type != 'H') && (type != 'V') && (type != 'B')
      print "fix #{@x},#{@y} recieved #{x},#{y} = #{n} : #{er}\n"
      if er != ""
        raise "fix : Parameter error"
      end
    end

    if !@fixed
    
      if n == @number
        raise "fix: I'm #{@x},#{@y} #{@number},  #{x},#{y} reqested #{n}"
      else
        @number = @number.delete(n)
      end

      # 候補がひとつになったらunoMembersに登録
      if @number.size == 1
        @table.unoMembers |= [[@x,@y]]
        print "fix: uno #{@x},#{@y} #{@number}\n" if $debugMode
      end

      case type
      when "H"
        member = @memberH
      when "V"
        member = @memberV
      when "B"
        member = @memberB
      end

      # 確定したものはメンバーから外す
      # 念のためメンバー以外からの要求だったら例外を発生させる。
      if member.delete([x,y]) == nil
        raise "fix: #{@x},#{@y} : #{x},#{y} is not a member"
      end
    end

  end


  ## ------------------------------------------
  ## ----  Set n into this cell               -
  ## ------------------------------------------
  #
  # 指定された文字列nを自分の値として確定させる。
  # '0'を指定された場合には現在の値で確定させる。
  # 確定後、関連セルへ確定を通知する。
  # リターン値として現在の値を返す
  #
  # 副作用として、通知先のセルの候補がひとつになったら
  # 表の値がひとつのセルのリスト(unoMembers)に追加する。
  #
  def set(n)

    # デバッグ用パラメータチェック
    if $debugMode
      er = ""
      er += "n is #{n.type} " if ! n.kind_of?(String)
      er += "n=#{n} "         if n.size != 1
      print "set #{@x},#{@y} = #{n} : #{er}\n"
      if er != ""
        raise "set : #{@x},#{@y} #{@number} <- #{n} : #{er}"
      end
    end

    # 確定済みだったら何もしない
    if !@fixed

      if n != '0'     # '0'は現在値の指定
        @number = n
      end
      
      @fixed = true
      @table.changed = true

      # 念の為、notFixedMembersとunoMembersから削除処理しておく。
      @table.notFixedMembers.delete([@x,@y])
      @table.unoMembers.delete([@x,@y])

      # 注・確定されたら以後処理されないので
      #     関連セルのメンバーリストの後始末処理は不要

      @memberH.each do |m|
        @table.cells[m[1]][m[0]].notice_from_fixed_cell(@x,@y,@number,"H")
      end

      @memberV.each do |m|
        @table.cells[m[1]][m[0]].notice_from_fixed_cell(@x,@y,@number,"V")
      end

      @memberB.each do |m|
        @table.cells[m[1]][m[0]].notice_from_fixed_cell(@x,@y,@number,"B")
      end

    end

    @number # 現在の候補値を返す
  end
  
  
  ## ------------------------------------------
  ## ----  Any member have the number ? -------
  ## ------------------------------------------
  #
  # 自分の候補値の中で、渡された関連セルのリスト上のセルが持たない値があるか調べる。
  # 自分だけの数値が有れば、その値ひとつとし、unoMembersに登録させる。
  def find_my_own_number_on_the_list(member)

    have_the_number = false

    @number.each_byte do |n|
      n = "" << n                # 文字コード --> 文字列 変換

      some_one_have_this = false
      member.each do |m|
        # 誰かがその文字を持っているなら、調査終了
        if @table.cells[m[1]][m[0]].do_you_have?(n)
          some_one_have_this = true
          break
        end
      end

      if ! some_one_have_this  # 誰も持っていなければ、このセルの値
        @number = "#{n}"    # このループの元だけれどrubyがよきに計らってくれる

        # 未確定な未処理リストから、値の確定した未処理リストへ移動
        @table.notFixedMembers.delete([@x,@y])
        @table.unoMembers |= [[@x,@y]]
        @table.changed = true
        have_the_number = true
        log(@table,[@x,@y],'*')
        
        break           # 解けるなら、ひとつのはず
      end
    end

    have_the_number
  end

  ## ------------------------------------------
  ## ----  I have unique number ? -------------
  ## ------------------------------------------
  #
  # 全ての関連セルに同じ数値を持つものが居ないかを調べる。
  # 自分だけの数値が有れば、その値ひとつとし、unoMembersに登録させる。
  #
  def find_my_own_number
    ret = false
    if ! @fixed 
      ret = find_my_own_number_on_the_list(@memberH) ||
            find_my_own_number_on_the_list(@memberV) ||
            find_my_own_number_on_the_list(@memberB)
    end
    ret
  end


  ## ------------------------------------------
  ## ---- Do you have this number ? -----------
  ## ------------------------------------------
  #
  # nで指定された候補を持っているか調べる。
  #
  def do_you_have?(n)
    /#{n}/ =~ @number
  end

  ## ------------------------------------------
  ## ---- Show Cell's data --------------------
  ## ------------------------------------------
  #
  # セルの内容を表示
  #
  def show
    print "Cell(#{@x},#{@y}) #{@number}\n"
  end

end

# ==========================================================

#
# 表のクラス
#
class DokuTable

    # DokuCellの２次元配列 @cells[y][x]
    attr_accessor :cells

    # 値が未確定なセルの位置(x,y)のリスト
    attr_accessor :notFixedMembers

    # 未確定だが値がひとつになったセルの位置(x,y)のリスト
    attr_accessor :unoMembers

    # 初期化に使われたデータ
    attr_accessor :data

    # 値が確定されたセルが有ると真を設定される
    attr_accessor :changed

    # 解く手順 [x,y,n] の記録
    attr_accessor :solved_path

    # 解く手順の記録開始
    attr_accessor :solved_path_on

  #
  # 表の初期化
  # 
  # 全てのセルを未確定で1-9の可能性を持ったセルとして作成する。
  #
  def initialize
    @cells = []
    @notFixedMembers = []
    @unoMembers = []
    @data = []
    @changed = false
    @solved_path_on = false
    @solved_path = []

    # 全てのセルを初期化
    for y in 0..8
      @cells[y] = []
      for x in 0..8
        @cells[y].push( DokuCell.new(x,y,0,self) )
      end
    end
    
    #全てのセルの関係を定義
    (0..8).each do |y|
      (0..8).each do |x|

        # x方向の関連セルのリストを作成、自分は外す
        (0..8).each do |i|
          cells[y][x].add_H_member([i,y]) if i != x
        end

        # y方向の関連セルのリストを作成、自分は外す
        (0..8).each do |i|
          cells[y][x].add_V_member([x,i]) if i != y
        end

        # 3x3ブロックの関連セルのリストを作成、自分は外す
        x0 = (x/3)*3
        y0 = (y/3)*3
        (0..2).each do |i|
          (0..2).each do |j|
            cells[y][x].add_B_member([(x0 + i),(y0 + j)]) if( ( x != (x0 + i)) || ( y != (y0 + j)) )
          end
        end
      end
    end
  end

  #
  # セルを data[ 0<= y <= 8 ][ 0<= x <= 8 ]の初期化用の数値配列で設定する。
  # 値が 0 の場合には何もしない。
  #
  def set_data(data)
    @data = data
    for y in (0..8)
      for x in (0..8)
        n = data[y][x]
        @cells[y][x].set(n.to_s) if n > 0
        p @unoMembers if $debugMode
      end
    end

    if $solved_path_on
      @solved_path_on = true
    end
  end

  #
  # 未確定のセル数を返す
  #
  def not_fixed_count
    notFixedMembers.size + unoMembers.size
  end

  #
  # 初期値データを出力する。
  #
  def output_initial_data
    print "|------Initial data ----| \n"
    for y in 0..8
      print "| "
      for x in 0..8
        str = @data[y][x].to_s
        str = (str == "0") ? "." : str
        sep = (2 == (x % 3)) ? "| " : ""
        printf "%s %s",str,sep
      end
      print "\n"
      if (y%3) == 2
        print "|-------+-------+-------| \n"
      end
    end
    print "\n"
  end

  #
  # ruby形式で初期値を出力する。
  #
  def output_initial_data_array
    print "$dataX = [\n"
    for y in 0..8
      print "[ "
      for x in 0..8
        str = @data[y][x].to_s
        sep = (2 == (x % 3)) ? " " : ""
        if x == 8
          printf "%s%s",str,sep
        else
          printf "%s,%s",str,sep
        end
      end
      if y == 8
        print "]\n"
      else
        print "],\n"
      end
    end
    print "]\n\n"
  end

  #
  # 解答を出力する。
  #
  def output_answer
    print "|------ answer data ----| \n"
    for y in 0..8
      print "| "
      for x in 0..8
        sep = (2 == (x % 3)) ? "| " : ""
        printf "%s %s",@cells[y][x].number, sep
      end
      print "\n"
      if (y%3) == 2
        print "|-------+-------+-------| \n"
      end
    end
    print "\n"
  end

  #
  # 解答手順を出力する。
  #
  def output_solved_path
    i = 0
    @solved_path.each do |log|
      print "#{log} "
      i += 1
      if i >= 5
        print "\n"
        i = 0
      end
    end
    print "\n" if i > 0
    print "\n"
  end


end

def log(table,m,mark=' ')
  if table.solved_path_on
    table.solved_path << "#{mark}[#{m[0]},#{m[1]}]=#{table.cells[m[1]][m[0]].number}"
  end
end

# ==========================================================


#
# 解答作成処理
#
# dataを読み込んで問題を解き、解答を標準出力に出す
#
def solve(data)
  debugMode = $debugMode
  $debugMode = false if ! $debugModeS

  print "< solve start >\n" if $debugMode

  solved = false            # まだ解けていない

  table = DokuTable.new     # 要素は全て空欄
  table.set_data(data)      # dataの中の値を表に設定

  ## ------------------------------------------
  ##---- Fixup all unknown cells --------------
  ## ------------------------------------------

  begin
    while table.not_fixed_count > 0
      table.changed = false

      # 単独の値の未処理セルを確定させる
      if table.unoMembers.size > 0
        table.unoMembers.each do |m|
          table.cells[m[1]][m[0]].set('0')
          log(table,m)
        end
      end
    
      # ひとつの値しか持たないセルを抽出
      if table.notFixedMembers.size > 0
        table.notFixedMembers.each do |m|
          table.cells[m[1]][m[0]].find_my_own_number
        end
      end
      
      if ! table.changed   # 変化無し？
        # 未処理メンバーが残っているのにループ内で何も変わらないなら無理だ
        if table.not_fixed_count > 0
          raise "LoopForever"
        end
      end
    end
    solved = true
  rescue => err   # ------------- 例外発生 -------------

    if $printout
      # 例外の表示
      printf "---------------------------------\n"
      printf "----!! Can't solve this !!-------\n"
      printf "---------------------------------\n"

      p err

      print "\n"
    end
  ensure # ---------- 終了処理 -----------------
    
    ## ------------------------------------------
    ## ----- Print out answer or error ----------
    ## ------------------------------------------
    
    table.output_initial_data if solved || $printout
    table.output_initial_data_array if solved && $initial_dataout
    table.output_answer if $printout || ($solved_ans && solved)
    table.output_solved_path if ($printout && $solved_path_on && solved)   ||
                                ($solved_ans && $solved_path_on && solved)

    #未確定があるなら先頭をヒント・セルに登録
    if table.notFixedMembers.size > 0
      x,y = table.notFixedMembers[rand(table.notFixedMembers.size)]
      $solveHint = [x,y,table.cells[y][x].number]
    end
  end

  print "< solve end >\n" if $debugMode
  $debugMode = debugMode

  solved
end

# ==================================================================

#
# 問題作成用
#
# 未処理のセルの中から順にひとつのセルを確定させる。
# 単一の値になった未処理を後回しにして、複数の値を持つセルから処理する。
#
# 方針の理由・単独の値を持つセルは既に決まっているセルから決定できる
# ということなので、後回しにした方が空欄数を稼げると思われる。
#
# $hintに探索時の未確定セル情報があれば、それを先に利用する。
#
def set_one_cell(table,data)
  print "< set_one_cell : start >\n" if $debug

  x,y,n = $solveHint
  if x != nil
    $solveHint = []
    n = n[rand(n.size),1]
    table.cells[y][x].set(n)
    data[y][x] = n.to_i
    print "< set_one_cell : end >\n" if $debug
    return
  end

  while (i = table.notFixedMembers.size) > 0
    i = rand(i)
    x,y = table.notFixedMembers[i]
    if ! table.cells[y][x].find_my_own_number     # 値が決まら無ければ
      i = rand(table.cells[y][x].number.length) # 持っている候補の中からランダムに選択
      n = table.cells[y][x].number[i,1]
      table.cells[y][x].set(n)
      data[y][x] = n.to_i
      print "< set_one_cell : end >\n" if $debug
      return
    end
  end

  if ( i = table.unoMembers.size ) > 0
    i = rand(i)
    x,y = table.unoMembers[i]
    n = table.cells[y][x].number  # 値はひとつのはず
    table.cells[y][x].set(n)
    data[y][x] = n.to_i
  else
    raise "set_one_cell: No member"   # 終わっているのに来た？
  end

  print "< set_one_cell : end >\n" if $debug
end

# ==================================================================

#
# 空欄だけの初期データ配列を作る
#
def new_data
  data = []
  for i in (0..8)
    data[i] = [0,0,0,0,0,0,0,0,0]
  end
  data
end

# ==================================================================

#
# 問題作成処理
#
# 出来たらTRUE、出来なかったらFALSE
#
def make
  print "< make : start >\n" if $debug
  
  $solveHint = []           # initialize Hint data
  table = DokuTable.new
  data  = new_data

  solved = false

  begin

  # サイエンス誌によると最低17個は必要だそうだ
  (1..17).each do |i|
    set_one_cell(table,data)
  end

  # 17で解けたらラッキー :-)
  solved = solve(data)


  # 解けるまでひとつづつ増やしながら試す
  while( (solved == false) && (table.not_fixed_count > $BlankLimit ) )
    set_one_cell(table,data)
    solved = solve(data)
  end

  print     "\n------- Not solved ------\n" if $debugMode && (! $solved)

  rescue => msg
    print "\n------- #{msg} ------\n" if $debugMode
  end

  print "< make : end >\n" if $debug
  solved
end


def help
  if $Exerb
	cmd = ExerbRuntime.filename()
	cmd.sub!(/.exe/,'')
  else
	cmd = 'ruby sudoku.rb'
  end

  print  "
Usage       使用方法

引数無しの時     : 標準入力から問題を読み込んで解答を出力します。
    #{cmd} 

引数がファイル名 : ファイルの中身を問題として読み込み解答を出力します。
    #{cmd} <fileName>

引数が make <n>  : make 2 の様に指定された場合には問題を指定された個数
                 : 出力します。
    #{cmd} make <n>

引数の前に -path が指定された場合、解く手順も出力されます。
    #{cmd} -path ...

引数の前に -help が指定された場合、このメッセージが出力されます。
    #{cmd} -help

問題は１行に空白またはカンマ','で区切られた9個の数が並ぶものとします。
その行が9行で１問です。この形式以外の場合、無視されます。
問題中の'.'は'0'に置き換えられます。'0'は空欄を意味します。
問題中の'|'は空白とみなされます。"

end

####------------------------------------------------------------######
####                   main                                     ######
####------------------------------------------------------------######


# -path 指定で解答手順を出力

while ARGV[0] =~ /^-/
  if ARGV[0] =~ /^-path/i
    $solved_path_on = true
    $solved_ans = true
  elsif ARGV[0] =~ /^-help/
    help
    exit
  end
  ARGV.shift
end

# 引数に make <n> が指定されたら問題作製モード、そうでなければ解答モード

# ----------- 問題作成要求 -------------------
if ARGV[0] =~ /^make/i
  $solved_ans = true if ARGV[0] =~ /^M/
  $initial_dataout = true if ARGV[0] =~ /i$/i

  if ARGV[1]
    $n = ARGV[1].to_i
  else
    $n = 1      # 作成個数のデフォルトは１個
  end

  # 要求された個数分作成
  (1..$n).each do |n|
    redo if ! make
  end

# ----------- スクリプト上の問題を解く -------------------
elsif ARGV[0] == '.' # internal data
  $printout = true
  for data in $dataList
    solve(data)
  end

# ----------- ファイルからの問題を解く -------------------
elsif ARGV[0]   # data file
  $printout = true
  n = 0
  data = []
  File.open(ARGV[0]) do |file|
    file.each_line do |line|
      line.gsub!(/[,\|\[\]]/,' ')
      line.gsub!(/\./,'0')
      if line =~/(\d)\s+(\d)\s+(\d)\s+(\d)\s+(\d)\s+(\d)\s+(\d)\s+(\d)\s+(\d)/
        n1,n2,n3,n4,n5,n6,n7,n8,n9 = $1,$2,$3,$4,$5,$6,$7,$8,$9
        data << [n1.to_i,n2.to_i,n3.to_i,n4.to_i,n5.to_i,n6.to_i,n7.to_i,n8.to_i,n9.to_i]
        n += 1
        if n == 9
          solve(data)
          n = 0
          data = []
        end
      end
    end
  end
  
# ----------- 標準入力からの問題を解く -------------------
else
  if STDIN.tty? 
    print "Plese input line data, like this\n"
    print "0 1 2 3 4 5 6 7 8 9 <return> 9 times\n"
    print "'0' or '.' is used as BLANK data\n\n"
    print "exit command is 'exit' or 'quit'\n"
  end

  $printout = true
  n = 0
  data = []
  while line = ARGF.gets
    line.chomp!
    break if line =~ /exit|quit/i
    
    line.gsub!(/[,\|\[\]]/,' ')
    line.gsub!(/\./,'0')
    if line =~/(\d)\s+(\d)\s+(\d)\s+(\d)\s+(\d)\s+(\d)\s+(\d)\s+(\d)\s+(\d)/
      n1,n2,n3,n4,n5,n6,n7,n8,n9 = $1,$2,$3,$4,$5,$6,$7,$8,$9
      data << [n1.to_i,n2.to_i,n3.to_i,n4.to_i,n5.to_i,n6.to_i,n7.to_i,n8.to_i,n9.to_i]
      n += 1
      if n == 9
        solve(data)
        n = 0
        data = []
      end
    end
  end

end