class Board
  class Space
    attr_accessor :value
    def initialize(value)
      @value = value
    end

    def empty?
      @value == 0
    end

    def to_s
      empty? ? " " : @value.to_s
    end
    alias :inspect :to_s

    def <=>(oth)
      @value <=> oth.value
    end
  end

  ROWS    = (0..8).collect { |i| Array.new(9) { |j| i*9 + j } }
  COLUMNS = (0..8).collect { |i| Array.new(9) { |j| j*9 + i } }
  BOXES   = (0..8).collect do |i|
    j = 27 * (i / 3) + 3 * (i % 3) # first row offset
    k = j + 9   # second row offset
    l = k + 9   # third row offset
    [j, j+1, j+2, k, k+1, k+2, l, l+1, l+2]
  end

  attr_reader :spaces
  def initialize(spaces)
    raise unless spaces.length == 81
    @spaces = spaces.collect { |s| s.is_a?(Space) ? s : Space.new(s) }
  end

  def row(index)
    @spaces.values_at(*ROWS[index])
  end
  
  def column(index)
    @spaces.values_at(*COLUMNS[index])
  end

  def box(index)
    @spaces.values_at(*BOXES[index])
  end

  def empty_spaces
    empties = []
    @spaces.length.times do |i|
      empties << i  if @spaces[i].empty? 
    end
    empties
  end

  def clone
    Board.new(@spaces.collect { |s| s.dup })
  end

  def valid?
    [:row, :column, :box].collect do |method|
      return false unless (0..8).collect { |i|
        set = send(method, i).select { |x| !x.empty? }
        set.collect! { |x| x.value }
        set.uniq == set
      }.all?
    end
    true
  end

  def complete?
    @spaces.collect { |s| !s.empty? }.all? && valid?
  end

  def to_s
    str = ""
    9.times do |i|
      row = row(i)
      str << "+-------" * 3 + "+\n"   if i % 3 == 0
      3.times { |j| str << "| %s %s %s " % row[(j*3)..(j*3+2)] }
      str << "|\n"
    end
    str + "+-------" * 3 + "+"
  end
end

class Solver
  def initialize(board)
    @board = board.clone
  end

  def solve
    empties = @board.empty_spaces
    empties.each_with_index do |space_i, i|
      (1..9).each do |j|
        @board.spaces[space_i].value = j
        next  unless @board.valid?
        return @board  if i == empties.length - 1
        b = Solver.new(@board).solve
        return b  if b
      end
    end
    nil
  end
end

board = Board.new([
  3,0,4,5,0,8,0,0,7,
  9,8,2,7,4,6,1,3,5,
  5,0,7,0,0,9,8,0,4,
  8,4,0,9,0,5,6,7,0,
  1,7,0,0,6,4,0,0,8,
  6,2,0,0,8,7,4,0,0,
  2,9,0,8,5,0,7,4,0,
  7,3,0,4,9,0,5,8,0,
  4,5,8,6,7,0,0,0,0
])
#puts "row 2"
#p board.row(2)
#puts "column 2"
#p board.column(2)
#puts "box 0"
#p board.box(0)
#puts "box 4"
#p board.box(4)
#puts "box 7"
#p board.box(7)
puts "======================"
puts board.to_s
puts "======================"
puts Solver.new(board).solve.to_s