#! 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 '[',']'
#   Ver. 3.05 2009/11/01 : Mt.Trail , add input-data-pattern(allow non-space format like 123456789)
#   Ver. 3.06 2009/11/23 : Mt.Trail , add block-line rule
#   Ver. 3.07 2009/11/29 : Mt.Trail , add group rule, -ng option
#   Ver. 4.00 2009/12/26 : Mt.Trail , Renew
#   Ver. 4.01 2009/12/27 : Mt.Trail , add -hi option
#
# -Memo-
#   2009/12/26 ver. 4.00
#   クラス構造の全面見直し。
#   未確定のグループ情報をcellからtable側に移動
#   対象を9x9の表だけに戻す。all clear Olympos data 
#
$rcs = "$Revision: 4.00 $ $Date: 2009/12/27 03:00:00 $"
$KCODE = "s"

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

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

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


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

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

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

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

# 解けない問題のみ出力
$ngFlag = false
#$ngFlag = true


#
# 初期データ
#   空欄部分は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]


# ---------------------------------
# １のビット数を数える
# ---------------------------------
def bits(n)
    num = (n >> 1) & 03333333333;
    num = n - num - ((num >> 1) & 03333333333);
    num = ((num + (num >> 3)) & 0707070707) % 077;
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
#  print "#{mark}[#{m[0]},#{m[1]}]=#{table.cells[m[1]][m[0]].number}\n"
end



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

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

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

  attr_accessor :x, :y     #位置は 0-8 とする
  attr_accessor :index3    #3セル単位でのインデックス
  attr_accessor :bn        #ブロック番号

  def fix(mark)
    @fixed = true      # 確定フラグ true=確定、false=未確定
    @table.notFixedMembers.delete([@x,@y])
    @table.unoMembers |= [[@x,@y]]
    @table.changed = true
    log(@table,[@x,@y],mark)
  end
  
  def unlink
#    @table.unoMembers.delete([@x,@y])
    @memberH.delete([@x,@y])
    @memberV.delete([@x,@y])
    @memberB.delete([@x,@y])
  end

  ## ------------------------------------------
  ## ----  Initialize Cell Data ---------------
  ## ------------------------------------------
  #
  # セルの初期化
  #   位置(x,y)と数値nを受け取り初期化する
  #   nがゼロの場合には空欄指定とし、1-9を可能性のある数値とする
  #
  def initialize(x,y,n,table)
    @bn = 3*(y/3).to_i + (x/3).to_i         # ブロック番号
    @memberH = table.h_list[y]              # 水平(x)方向の関連セルのリスト
    @memberV = table.v_list[x]              # 垂直(y)方向の関連セルのリスト
    @memberB = table.b_list[@bn]            # 3x3ブロックの関連セルのリスト

    @number = ""        # 可能性のある数値の文字列 '1'-'9'で構成される
    @x = x              # x 位置 0..8
    @y = y              # y 位置 0..8
    @index3 = {}
    @index3['H']  = @ih = (x/3).to_i   # 水平ラインでの3セル単位での位置
    @index3['V']  = @iv = (y/3).to_i   # 垂直ラインでの3セル単位での位置
    @index3['BH'] = @ibh= x % 3        # ブロック内水平方向の位置
    @index3['BV'] = @ibv= y % 3        # ブロック内垂直方向の位置
    
    @table = table      # 所属する表

    # 初期値が０の場合には空欄なので1-9の可能性あり、その他の場合には指定値を初期値とする
    if (n == 0)
      @fixed = false      # 確定フラグ true=確定、false=未確定
      @number =  "123456789"
      @table.notFixedMembers.push([@x,@y])
      @memberH.push([@x,@y])
      @memberV.push([@x,@y])
      @memberB.push([@x,@y])
    else
      fix("i")
      @number ="#{n}"     # 候補データは文字列
    end
  end
  
  ## ------------------------------------------
  ## ----  Delete fixed number and the member -
  ## ------------------------------------------
  #
  # (x,y)で指定されたセルがnに確定された通知を受け取る。
  #
  # 既に自分が確定していれば以下の処理はしない。
  # 確定されたnを自分の可能性リストから外す。
  # 自分の候補がひとつになったら表のunoMembersに登録する。
  #
  # index = (0,1,2): 非対象ブロックインデックス, nil:非対象指定なし
  #
  def notice_from_fixed_cell(x,y, n, type=nil, index=nil)
#    print "[#{@x},#{@y}] notice_from_fixed_cell(#{x},#{y}, #{n}, #{type},#{index})\n"

    # デバッグ用パラメータチェック
    if $debugMode && (!@fixed)
      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
      print "fix #{@x},#{@y} recieved #{x},#{y} = #{n} : #{er}\n"
      if er != ""
        raise "fix : Parameter error"
      end
    end
    return if (x == @x) && (y == @y) # 自分自身からの通知は無視する
    return if type && (index == @index3[type])  # 非対象の指定が一致すれば通知は無視する

#    print "[#{@x},#{@y}] notice_from_fixed_cell(#{x},#{y}, #{n}, #{type},#{index})\n"

    if @fixed
      if n == @number
        raise "fix: I'm #{@x},#{@y} #{@number},  #{x},#{y} reqested #{n}"
      end
    else
      if @number.delete!(n)
        @table.changed = true
      end
      print "-->#{@number}\n" if $debugMode
      
      # 候補がひとつになったらfix
      if @number.size == 1
        fix('n')
        print "fix: uno #{@x},#{@y} #{@number}\n" if $debugMode
      end
    end

  end

  ## ------------------------------------------
  ## ----  Nortify                            -
  ## ------------------------------------------
  def notice_to_members(member)
    member.each do |m|
      @table.cells[m[1]][m[0]].notice_from_fixed_cell(@x,@y,@number)
    end
  end
  
  def notice
    print "Notice [#{@x},#{@y}]=#{@number}\n" if $debugMode
    notice_to_members(@memberH)
    notice_to_members(@memberV)
    notice_to_members(@memberB)
  end


  ## ------------------------------------------
  ## ----  Set n into this cell               -
  ## ------------------------------------------
  #
  # 指定された文字列nを自分の値として確定させる。
  # '0'を指定された場合には現在の値で確定させる。
  # リターン値として現在の値を返す
  #
  #
  def set(n)

#    print "< set(#{n})\n" if $debugMode
#    print "[#{@x},#{@y}] set(#{n})\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
      
      fix('s')
    end
#    print " /set(#{n}) >\n" if $debugMode

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

#    print "< find_my_own_number_on_the_list(#{member})\n" if $debugMode

    have_the_number = false

    own_number = nil
    @number.each_char do |n|
      some_one_have_this = false
      member.each do |m|
        if m != [@x,@y]  # 自分でない時
          # 誰かがその文字を持っているなら、調査終了
          if @table.cells[m[1]][m[0]].do_you_have?(n)
            some_one_have_this = true
            break
          end
        end
      end

      if ! some_one_have_this  # 誰も持っていなければ、このセルの値
        own_number = "#{n}"
        break;
      end
    end

    if own_number != nil
      @number = own_number
      fix('o')
      have_the_number = true
    end
#    print " /find_my_own_number_on_the_list(#{member}) >\n" if $debugMode

    have_the_number
  end

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


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

  ## ------------------------------------------
  ## ---- Block Line has unique number ?  -----
  ## ------------------------------------------
  #
  # 自分の持っている番号をtableの縦横のブロックlineに演算する。
  # 元が0xF(全ブロック+未処理検出ビット)で初期化されていて、
  # ブロックのビットでandを取ることで番号の存在するブロック以外を
  # 消していく、結果として同じブロックにのみ数値が有るものだけが
  # 1ビットのみ立った値として残る。

  def line_check
    return if @fixed
    @number.each_byte do |n|
      n = n - 49                # 文字コード --> 数値変換 '1' --> 0

      @table.h_line[@y][n]   &= (1 << @ih)
      @table.v_line[@x][n]   &= (1 << @iv)
      @table.bh_line[@bn][n] &= (1 << @ibh)
      @table.bv_line[@bn][n] &= (1 << @ibv)
    end
  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

    #水平、垂直、ブロックの未確定のメンバーリスト
    attr_accessor :h_list
    attr_accessor :v_list
    attr_accessor :b_list
    
    # 未確定だが値がひとつになったセルの位置(x,y)のリスト
    attr_accessor :unoMembers

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

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

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

    # 解く手順の記録開始
    attr_accessor :solved_path_on
    
    #ブロック内のLine上での確定を検査するための配列 h_line[n][1..9]
    attr_accessor :h_line
    attr_accessor :v_line
    attr_accessor :bh_line
    attr_accessor :bv_line
#    attr_accessor :h_pos
#    attr_accessor :v_pos
#    attr_accessor :bh_pos
#    attr_accessor :bv_pos

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

    for i in 0..8
      @h_list[i] = []
      @v_list[i] = []
      @b_list[i] = []
    end
    
    # 全てのセルを初期化
    for y in 0..8
      @cells[y] = []
      for x in 0..8
        @cells[y].push( DokuCell.new(x,y,0,self) )
      end
    end
  end

  #
  # セルを data[ 0<= y <= 8 ][ 0<= x <= 8 ]の初期化用の数値配列で設定する。
  # 値が 0 の場合には何もしない。
  #
  def set_data(data)
    @solved_path_on = true if $solved_path_on
    @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
  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)) ? "| " : ""
        if $ngFlag
          printf "%5s %s",@cells[y][x].number, sep
        else
          printf "%s %s",@cells[y][x].number, sep
        end
      end
      print "\n"
      if (y%3) == 2
        if $ngFlag
          print "|-------------------+-------------------+-------------------| \n"
        else
          print "|-------+-------+-------| \n"
        end
      end
    end
    print "\n"
    print "\f" if $ngFlag
  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

  def set_blocks_line
    @h_line = []
    @v_line = []
    (0..8).each do |i|
      @h_line[i] =  [0xF,0xF,0xF,0xF,0xF,0xF,0xF,0xF,0xF]
      @v_line[i] =  [0xF,0xF,0xF,0xF,0xF,0xF,0xF,0xF,0xF]
      @bh_line[i] =  [0xF,0xF,0xF,0xF,0xF,0xF,0xF,0xF,0xF]
      @bv_line[i] =  [0xF,0xF,0xF,0xF,0xF,0xF,0xF,0xF,0xF]
    end
  end

#  def clear_blocks_pos
#    @h_pos = []
#    @v_pos = []
#    (0..8).each do |i|
#      @h_pos[i] =  [0,0,0,0,0,0,0,0,0]
#      @v_pos[i] =  [0,0,0,0,0,0,0,0,0]
#      @bh_pos[i] =  [0,0,0,0,0,0,0,0,0]
#      @bv_pos[i] =  [0,0,0,0,0,0,0,0,0]
#    end
#  end

  ##
  ## 縦横のラインの中でブロックの中だけにある数値が有れば
  ## そのブロック中の並行するラインには同じ数値は有りえない
  ##
  def line_check_on_the_line(line)
    line.each_with_index do |h,k|
#p h
      h.each_with_index do |dt,n|
        if (dt==1)||(dt==2)||(dt==4)
          dt = 3 if dt == 4
          dt -= 1
          yield(k,n,dt)
        end
      end
    end
  end

  def line_check
#output_answer
    line_check_on_the_line(@h_line) do |k,n,index|
      @b_list[3*((k/3).to_i)+index].each do |m|
        @cells[m[1]][m[0]].notice_from_fixed_cell(index*3,k,(n+1).to_s,'BV',k%3)
      end
    end

#output_answer
    line_check_on_the_line(@v_line) do |k,n,index|
      @b_list[(index*3)+((k/3).to_i)].each do |m|
        @cells[m[1]][m[0]].notice_from_fixed_cell(k,index*3,(n+1).to_s,'BH',k%3)
      end
    end

#output_answer
    line_check_on_the_line(@bh_line) do |k,n,dx|
      ix = k%3
      x = 3*ix + dx
      iy = (k/3).to_i
      y = iy*3
      @v_list[x].each do |m|
        @cells[m[1]][m[0]].notice_from_fixed_cell(x,y,(n+1).to_s,'V',iy)
      end
    end

#output_answer
    line_check_on_the_line(@bv_line) do |k,n,dy|
      ix = k%3
      x = 3*ix
      iy = (k/3).to_i
      y = iy*3+dy
      @h_list[y].each do |m|
        @cells[m[1]][m[0]].notice_from_fixed_cell(x,y,(n+1).to_s,'H',ix)
      end
    end
  end
  
end

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


#
# 解答作成処理
#
# dataを読み込んで問題を解き、解答を標準出力に出す
#
def solve(data,comment = '')
  debugMode = $debugMode
  $debugMode = false if ! $debugModeS
  ng = false
  
  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
        unoMembers = table.unoMembers
        table.unoMembers = []
        unoMembers.each do |m|
          table.cells[m[1]][m[0]].notice
          table.cells[m[1]][m[0]].unlink
        end
      end
    
      # ひとつの値しか持たないセルを抽出
      if table.notFixedMembers.size > 0
        notFixedMembers = table.notFixedMembers.dup
        notFixedMembers.each do |m|
          table.cells[m[1]][m[0]].find_my_own_number
        end
      end

      next if table.changed

      table.set_blocks_line()
      notFixedMembers = table.notFixedMembers.dup
      notFixedMembers.each do |m|
        table.cells[m[1]][m[0]].line_check
      end
      table.line_check
      
      next if table.changed

      if ! table.changed   # 変化無し？
        # 未処理メンバーが残っているのにループ内で何も変わらないなら無理だ
        if table.not_fixed_count > 0
          raise "LoopForever"
        end
      end
    end
    solved = true
  rescue => err   # ------------- 例外発生 -------------

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

      p err

      print "\n"
    end
  ensure # ---------- 終了処理 -----------------
    
    if ($ngFlag && ng)||(!$ngFlag)
      ## ------------------------------------------
      ## ----- Print out answer or error ----------
      ## ------------------------------------------
      print comment
      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)
    end

    #未確定があるならランダムに選択したセルをヒント・セルに登録
    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 update(table)
  # 単独の値の未処理セルを確定させる
  while table.unoMembers.size > 0
    unoMembers = table.unoMembers
    table.unoMembers = []
    unoMembers.each do |m|
      table.cells[m[1]][m[0]].notice
      table.cells[m[1]][m[0]].unlink
    end
  end
end

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)
    update(table)
    data[y][x] = n.to_i
    print "< set_one_cell : end >\n" if $debug
    return
  end

  i = 0
  while (i = table.notFixedMembers.size) > 0
    i = rand(i)
    x,y = table.notFixedMembers[i]
    if ! table.cells[y][x].find_my_own_number     # 値が決まら無ければ
      update(table)
      i = rand(table.cells[y][x].number.length) # 持っている候補の中からランダムに選択
      n = table.cells[y][x].number[i,1]
      table.cells[y][x].set(n)
      update(table)
      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)
    update(table)
    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)


  # 解けるまでひとつづつ増やしながら試す
  set_count = 17
#  while( (solved == false) && (table.not_fixed_count > $BlankLimit ) )
  while( (solved == false) && (81 > set_count+$BlankLimit ) )
    set_one_cell(table,data)
    set_count += 1
    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

引数の前に -ng が指定された場合、解けなかった問題がが出力されます。
    #{cmd} -ng

問題作成時に、引数の前に -hi が指定された場合、空白の多い問題を作成します。
ただし、作成に大幅に時間がかかるようになります。
    #{cmd} -hi make <n>

問題は１行に空白またはカンマ','で区切られた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] =~ /^-ng/
    $ngFlag = true
  elsif ARGV[0] =~ /^-hi/
    $BlankLimit = $BlankLimit_Hight
  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 = []
  comment = ""
  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)/) ||
         (line =~/(\d)(\d)(\d)(\d)(\d)(\d)(\d)(\d)(\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,comment)
          n = 0
          data = []
        end
      elsif line =~ /^#/
        n = 0
        data = []
        comment = line if line =~ /^#-/
      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)/) ||
         (line =~/(\d)(\d)(\d)(\d)(\d)(\d)(\d)(\d)(\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