From: David Tran <email55555@...>
Date: 2005-08-24T07:11:19+09:00
Subject: Re: [QUIZ] Sodoku Solver (#43)

Slightly modified, during the reduce once, 
the while loop may reduce some cells to unique possibility number,
so set back to the cells data to reduce brute force steps.


class Sodoku
  attr_reader :solutions
  
  def initialize( input )
    @cells = Array.new(81)
    @possibilities = {}
    @solutions = 0
    index = 0
    input.to_s.scan(/./) do |c|
      case c
        when '1'..'9' : @possibilities[index] = [ @cells[index] = c.to_i ]
        when '_'      : @possibilities[index] = (1..9).to_a 
        else next
      end
      break if (index += 1) == 81
    end
    # raise "Input data incomplete" if index != 81
  end

  def solve
    return false unless reduce_possibilities  # reduce only once then
    return _solve(0)                          # brute force to solve it
  end

  def show_all_solutions
    return unless reduce_possibilities  # reduce only once then
    _solve_all(0)                       # brute force to solve all solutions
  end

  # to_s borrow from Simon ...
  def to_s
    "+-------+-------+-------+\n| " +
    Array.new(3) do |br|
      Array.new(3) do |r|
        Array.new(3) do |bc|
          Array.new(3) do |c|
            @cells[br*27 + r * 9 + bc * 3 + c] || "_"
          end.join(" ")
        end.join(" | ")
      end.join(" |\n| ")
    end.join(" |\n+-------+-------+-------+\n| ") +
    " |\n+-------+-------+-------+\n"
  end 

  private
  
  # The cell's neighborhoods are cells need to check to be sure no duplicate
  # value with the cell. It has exactly 20 cells neighborhoods per cell.
  NEIGHBORHOODS = Array.new(81) do |index| 
    row, col = index / 9, index % 9
    r, c = row / 3 * 3, col / 3 * 3
    ary = []
    9.times do |i| 
      ary << (i * 9 + col)               # add cells at the same column 
      ary << (row * 9 + i)               # add cells at the same row
      ary << ((i/3) + r) * 9 + (i%3) + c # add cells at the same 3x3 box
    end
    ary.uniq - [index]
  end
  
  def reduce_possibilities
    index = number = nil
    while @possibilities.find { |index, number| number.size == 1 }
      @cells[index] = number[0]  # add this line compare to previous program
      @possibilities.delete(index)
      neighborhoods = NEIGHBORHOODS[index]
      @possibilities.each do |key, value|
        next unless neighborhoods.include?(key)
        value -= number
        if value.size == 0
          return false  # invalid input data
        else
          @possibilities[key] = value
        end
      end
    end
    true
  end
  
  def _solve(start)
    start.upto(80) do |index|
      next if @cells[index]
      @possibilities[index].each do |value|
        next if NEIGHBORHOODS[index].any? { |i| @cells[i] == value }
        @cells[index] = value
        _solve(index + 1) ? (return true) : @cells[index] = nil
      end
      return false
    end
    true
  end
  
  def _solve_all(start)
    start.upto(80) do |index|
      next if @cells[index]
      @possibilities[index].each do |value|
        next if NEIGHBORHOODS[index].any? { |i| @cells[i] == value }
        @cells[index] = value
        _solve_all(index + 1)
        @cells[index] = nil
      end
      return
    end
    @solutions += 1
    puts self
  end    
end


if __FILE__ == $0
  input = ''
  while line = gets
    input << line
  end

  sodoku = Sodoku.new(input)
  puts sodoku.solve ? sodoku : "No solution"
  
  # sodoku = Sodoku.new(input)
  # sodoku.show_all_solutions
  # puts "Total #{sodoku.solutions} solutions." 
end