【Ruby】【アルゴリズム】数独を解く。プログラミング言語Ruby 学習感想文 ～1章

　
「はてなブックマーク」っていう概念が分からない
はてなのことが全然分かってない。

　
この本を読んでいます。

プログラミング言語 Ruby

1章の「数独ソルバ」を書きました。
　

備考

以下のコードはほとんど記載のコードと同じだけど、
少し違うところがあります。
　
変えたところ。

変数名「p」
フラグを否定形から肯定形に
変数名をキャメル命名からスネーク命名に
引数と同じ変数名は使わない。

一応お断りということで。

学んだこと

• 配列演算子の再定義の方法
• dupメソッドの再定義方法
• 独自イテレータの定義方法
• 複数の返り値を設定する場合、returnを明示

もっといっぱいあるけど。

dupメソッドの再定義

b = a.dup

と書いた場合、
aの状態は変更せず、
新しく生成したオブジェクト（参照情報）をbに渡す、
と普通考えると思うのですが、ここのメソッドは、
　
今までのオブジェクトをbに渡して、
新しくaの参照先を変える、というやり方。
　
具体的にはこう↓

def dup
  copy = super
  @grid = @grid.dup #コピー元の参照先を変更
  copy
end

　
最初見たときは
「えー。このコードでどうやってcopyオブジェクトに
複製した@gridの参照先を渡してるの？？」
と思ったけど、「渡してない」ことがポイントなんだね。
目からウロコ。

複数の返り値を設定する場合、returnを明示

･･･
  return rmin, cmin, pmin
end

returnを省略すると構文エラー。←誤りでしたごめんなさい。
※訂正、

  [rmin, cmin, pmin]

と配列化する事によってreturnを明示しなくても複数の値を返せる（10月7日追記）
　

コード全量

module Sudoku
  class Puzzle
    ASCII = ".123456789"
    BIN = "\000\001\002\003\004\005\006\007\010\011"
    def initialize(data)
      if data.respond_to?(:join)
        s = data.join 
      else
        s = data.dup
      end
      s.gsub!(/\s/, "")
      raise Invalid , "wrong size" if s.length != 81
      if i = s.index(/[^123456789\.]/)
        raise Invalid , "wrong character #{s[i]} in pazzle" 
      end
      s.tr!(ASCII, BIN)
      @grid = s.unpack('c*')
      raise Invalid , "data has duplicates" if has_duplicates?
    end
    def to_s
      result = ""
      0.upto(8) do |i|
         result += @grid[i*9,9].pack('c9').tr!(BIN, ASCII) + "\r\n"
      end
      result
    end
    def rowdigits(row)
       @grid[9*row, 9] -[0]
    end
    def coldigits(col)
      result = []
      col.step(80, 9) do |i|
        v = @grid[i]
        result << v if v != 0
      end
      result
    end
    BoxToIndex = [0,3,6,27,30,33,54,57,60].freeze
    def boxdigits(box)
      i = BoxToIndex[box]
      [@grid[i], @grid[i+1], @grid[i+2],
       @grid[i+9], @grid[i+10], @grid[i+11],
       @grid[i+18], @grid[i+19], @grid[i+20]] - [0]
    end
    def has_duplicates?
      0.upto(8){|row| return true if rowdigits(row).uniq!}
      0.upto(8){|col| return true if coldigits(col).uniq!}
      0.upto(8){|box| return true if boxdigits(box).uniq!}
      false
    end
    def [](row, col)
      @grid[row*9+col]
    end
    def []=(row, col, newval)
      raise Invalid, "ilegal cell value: #{newval}" if !(0..9).include?(newval)
      @grid[row*9+col] = newval
    end
    def dup
      copy = super
      @grid = @grid.dup #コピー元の参照先を変更
      copy
    end
    BoxOfIndex =[
      0,0,0,1,1,1,2,2,2,0,0,0,1,1,1,2,2,2,0,0,0,1,1,1,2,2,2,
      3,3,3,4,4,4,5,5,5,3,3,3,4,4,4,5,5,5,3,3,3,4,4,4,5,5,5,
      6,6,6,7,7,7,8,8,8,6,6,6,7,7,7,8,8,8,6,6,6,7,7,7,8,8,8].freeze
    def each_unknown
      0.upto(8) do |row|
        0.upto(8) do |col|
          index = row*9 + col
          next if @grid[index] != 0
          box = BoxOfIndex[index]
          yield(row, col, box)
        end
      end
    end
    def possible(row, col, box)
      [1,2,3,4,5,6,7,8,9].freeze-(rowdigits(row)+coldigits(col)+boxdigits(box))
    end
  end
  def Sudoku.scan(puzzle)
    changed = true
    while changed
      changed = false
      rmin, cmin, pmin = nil
      min = 10
      puzzle.each_unknown do |row, col, box|
        possibles = puzzle.possible(row, col, box)
        if possibles.length == 0
          raise Impossible, "cant solve"
        elsif possibles.length == 1
          puzzle[row, col] = possibles[0]
          changed = true
        else
          # 1箇所でも値を確定できたら以降は最小値チェックはせず,
          # それまでのrmin cmin pmin の情報はリセット.
          # 確定後のpuzzleを対象にeach_unknownを繰り返す
          if !changed && possibles.length < min 
            min = possibles.length
            rmin, cmin, pmin = row, col, possibles
          end
        end
      end
    end
    return rmin, cmin, pmin
  end
  def Sudoku.solve(puzzle)
    _puzzle = puzzle.dup
    row, col, possible = scan(_puzzle)
    return _puzzle if row.nil?
    possible.each do |pos|
      _puzzle[row, col] = pos
      begin
        return solve(_puzzle)
      rescue Impossible
        next
      end
    end
    raise Impossible, "cant solve"
  end
  class Invalid < StandardError ;end
  class Impossible < StandardError ;end
end

test_data = ["1..", "42.", "...", "...", "8..", "2..", "4..", "..1", "..8", "..4", "..3", ".9.", "..9", ".4.", "...", "...", "...", ".1.", ".35", "...", "...", "...", ".39", ".6.", "7.2", ".6.", ".54"]

a = Sudoku::Puzzle.new(test_data)
puts Sudoku.solve(a)

　
　
■実行結果

158427936
973856241
426391578
284713695
319645827
567982413
635274189
841539762
792168354

今日は正規化と文字コードを学ぶ。。。