数独ソルバー

another_sudoku_solver.rb

module Sudoku
  Size = 81
  Length = 9
  
  INDEXS = [0, 3, 6, 27, 30, 33, 54, 57, 60]
    .map { |i| [i, i+1, i+2, i+9, i+10, i+ 11, i+18, i+19, i+20] }
  
  class CertainMap
    def initialize(ary)
      @field = ary
    end
    attr_reader :field
    
    def make_possible_map
      PossibleMap.new(self)
    end
    
    def each_certain_number
      @field.each_with_index do |num, i|
        yield(num, i) if num.nonzero?
      end
    end
    
    def solved?
      @field.none? { |num| num.zero? }
    end
    
    def inspect
      @field.each_slice(Length).map {|row|
        row.map { |i| i.zero? ? "." : i.to_s }.join
      }.join("\n")
    end
    
    alias :to_s :inspect
  end
  
  class PossibleMap
    def initialize(certain_map)
      @c_map = certain_map
      @field = Array.new(Size) { [*1..Length] }
      @field.map!.with_index {|e, i|
        x = @c_map.field[i]
        x == 0 ? e : [x]
      }
    end
    attr_reader :c_map
    attr_accessor :field
    
    def inspect
      @field.map(&:join).each_slice(Length).map { _1.join(" ") }
    end
    
    def each_element(i)
      x = i % Length
      y = i / Length
      
      (y * Length...(y + 1) * Length).each do |j|
        if j != i && @field[j].size != 1
          yield @field[j]
        end
      end
      Length.times do |i1|
        j = i1 * Length + x
        if j != i && @field[j].size != 1
          yield @field[j]
        end
      end
      INDEXS[ y / 3 * 3 + x / 3].each do |j|
        if j != i && @field[j].size != 1
          yield @field[j]
        end
      end
    end
    
    def update1!
      changed = false    #変更があったか
      @c_map.each_certain_number do |num, idx|
        each_element(idx) do |e|
          f = e.delete(num)
          changed = true if f
        end
      end
      @c_map = make_certain_map
      changed
    end
    
    def update2!
      changed = false    #変更があったか
      (1..Length).each do |kind|
        changed = true if update2_sub(kind)
      end
      @c_map = make_certain_map
      changed
    end
    
    def update2_sub(kind)
      changed = false
      all_blocks do |blocks|
        e = search_one(blocks, kind)
        next unless e
        @field[e[1]] = [kind]
        changed = true
      end
      changed
    end
    
    #1つの行（列）に「確定しているkind」がない場合、他の「確定している数字」を消す。
    #そして、「kindを含むelement」が列に１つだけある場合、その「確定しているkind」が決まる。
    def search_one(blocks, kind)
      return nil unless blocks.none? { |block| block[0] == [kind] }
      bs = blocks.filter_map { |b| !b[0].include?(kind) || b[0].size == 1 ? nil : b }
      bs.size == 1 ? bs[0] : nil
    end
    
    def all_blocks
      Length.times do |y|
        yield Length.times.map { [@field[j = y * Length + _1], j] }
      end
      Length.times do |x|
        yield Length.times.map { [@field[j = _1 * Length + x], j] }
      end
      Length.times do |i| 
        yield INDEXS[i].map { [@field[_1], _1] }
      end
    end
    
    def make_certain_map
      tmp = @field.map {|e|
        case e.size
        when 0
          raise
        when 1
          e[0]
        else
          0
        end
      }
      CertainMap.new(tmp)
    end
    
    def solved?
      @c_map.solved?
    end
    
    def dup
      tmp = self.field
      pm = PossibleMap.new(@c_map)
      pm.field = tmp
      pm
    end
    
    def min
      @field.map.with_index { |e, i| [e, i] }
        .reject { _1[0].size == 1 }.min_by { _1[0].size }
    end
  end
  
  
  module_function
  
  def solve(init_map)
    im = init_map.flat_map { _1.chomp.chars.map(&:to_i) }
    cm = CertainMap.new(im)
    pm = cm.make_possible_map
    
    update(pm)
    puts pm.c_map
    
    pm = try(pm) unless pm.solved?
    
    puts pm.c_map
  end
  
  def update(pm)
    loop do
      f1 = update1(pm)
      f2 = update2(pm)
      break if !f1 && !f2
    end
  end
  
  def update1(pm)
    f1 = false
    loop do
      f = pm.update1!
      f1 = true if f
      break unless f
    end
    f1
  end
  
  def update2(pm)
    f2 = false
    loop do
      f = pm.update2!
      f2 = true if f
      break unless f
    end
    f2
  end
  
  def try(pm)
    return pm if pm.solved?
    tmp = pm.dup
    e, idx = tmp.min
    p [e, idx]
    
    exit
    #再帰
  end
end

Sudoku.solve(DATA.readlines)

=begin
=end
__END__
004000000
205001800
000800003
090000000
000070060
108005300
030009000
040000200
902050007

sudoku_solver.rb

module Sudoku
  Rows = 9.times.map {|i|
    (i * 9).upto(i * 9 + 8).to_a
  }
  Cors = 9.times.map {|i|
    i.step(80, 9).to_a
  }
  make = ->(i) {[i,i+1,i+2,i+9,i+10,i+11,i+18,i+19,i+20]}
  Blocks = [0,3,6,27,30,33,54,57,60].map(&make)
    
  module_function
  
  def each_section(*types)
    types.each do |type|
      type.each do |idxs|
        yield idxs.map { @field[_1] }
      end 
    end
  end
  
  def delete(a, b)
    b.each { a.delete(_1) }
  end
  
  def flatten(idx)
    ary = @field[idx]
    if ary.size == 1
      @field[idx] = ary[0]
      reduct
    end
  end
  
  def reduct
    each_section(Rows, Cors, Blocks) do |section, _|
      integers = section.select { _1.instance_of?(Integer) }
      section.each { delete(_1, integers) if _1.instance_of?(Array) }
    end
  end
  
  def think
    loop do
      tmp = @field.map(&:dup)
      reduct
      @field.each_index do
        flatten(_1) if @field[_1].instance_of?(Array)
      end
      break if @field == tmp
    end
    finish if @field.all? { _1.instance_of?(Integer) }
  end
  
  def finish
    puts @field.each_slice(9).map(&:join)
    exit
  end
  
  def select_idxs(field)
    [*0...81].select { field[_1].instance_of?(Array) }
      .sort_by { field[_1].size }
  end
  
  def backtracking(field)
    idxs = select_idxs(field)
    while (idx = idxs.shift)
      field[idx].each do |int|
        @field = field.map(&:dup)
        @field[idx] = int
        think
        backtracking(@field)
      end
    end
  end
  
  def check(field, tmp = nil)
    each_section(Rows, Cors, Blocks) do |section, _|
      f = section.select { _1.instance_of?(Integer) }
            .tally.select { |k, v| v >= 2 }.empty?
      unless f
        p tmp if tmp
        p field
        raise "error!"
      end
    end
  end
  
  def solve(data)
    @field = data.flat_map {
      _1.chars.map { |c| c == "." ? (1..9).to_a : c.to_i }
    }
    think
    backtracking(@field)
  end
end

Sudoku.solve(DATA.readlines(chomp: true))

__END__
3.61....7
1.....2.9
7..864..1
.....8...
.3..1..9.
.....5...
4..731..5
5.....9.4
8.14....6