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

Here is my solution, just uses backtracking and simple algorithm, no
complex strategics.

class Sodoku
  
  def initialize( input )
    @ary = Array.new(9) { Array.new(9) }  # 9 rows x 9 columns
    index = 0
    input.to_s.scan(/./) do |c|
      case c
        when '1'..'9' : @ary[index / 9][index % 9] = c.to_i
        when '_'      : # skip
        else next
      end
      break if (index += 1) == 9 * 9
    end
    # raise "Input data incomplete" if index != 9 * 9
  end

  def solve
    9.times do |row|
      9.times do |col|
        next if @ary[row][col]
        
        # find next possible value for @ary[row][col]
        1.upto(9) do |v|          
          # check on same row/col, no any col/row already used it
          next unless 9.times { |i| break if @ary[i][col] == v ||
@ary[row][i] ==v }
          
          # check on 3x3 box, no other cell already used it
          next unless 3.times do |i|
            break unless 3.times do |j|
              break if @ary[i + row / 3 * 3][j + col / 3 * 3] == v
            end
          end
          
          @ary[row][col] = v

          if solve
            return true
          else
            @ary[row][col] = nil  # backtracking
          end          
        end
        
        return false
      end
    end
    true
  end
  
  def to_s
    s = "+-------+-------+-------+\n"
    @ary.each_with_index do |row, index|
      row = row.map { |e| e ||= '_' } * ' '
      row[6,0] = row[12,0] = '| '
      s << '| ' << row << " |\n"
      s << "+-------+-------+-------+\n" if [2, 5, 8].include?(index)
    end
    s
  end
end

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

  sodoku = Sodoku.new(input)
  puts sodoku.solve ? sodoku : "No solution"
end