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

Speed up my program ...

It seems difficult and low performace to backtracting possibilities data set ...
I did try to duplicate possibilities data and each guess to reduce the
possibilities data set.
But it is slow then just using brute force.
( Time is wasted on recursive process on the possiblilities data set
maintenance/creation )

This version will just reduce the possibilities data set only once
then using brute force.
It is much faster than my previous program ( of course, it is slower
than others good program ... )
--------------------------------------------

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 }
      @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