#
# Magic matrix solver
# Ken Nishimura 2011/9/14
#
# Solver.new(Matrix.new((1..9))).solve yeilds:
# 
# |8|1|6|
# |3|5|7|
# |4|9|2|
#

class Numeric
  def square_number?
    Math.sqrt(self).integer?
  end
end

class Float
  def integer?
    self.ceil == self
  end
end

module MagicMatrix
  module Utils
    def magic_constant
      @magic_constant ||= @items.inject(:+) / @order
    end

    def [](x, y)
      @matrix[x + y * @order]
    end

    def []=(x, y, n)
      @matrix[x + y * @order] = n
    end

    def top_left; @matrix[0]; end
    def top_right; @matrix[@order - 1]; end
    def buttom_left; @matrix[@order * (@order - 1)]; end
    def buttom_right; @matrix[@order**2 - 1]; end

    def column_indices(x)
      (0..(@order - 1)).map{|i| i * @order + x}
    end

    def row_indices(y)
      (0..(@order - 1)).map{|i| i + @order * y}
    end

    def diagonal_indices1
      (0..(@order - 1)).map{|i| (@order + 1) * i}
    end

    def diagonal_indices2
      (1..@order).map{|i| (@order - 1) * i}
    end

    def sum_cells(indices)
      indices.inject(0) {|sum, i| sum += @matrix[i]}
    end

    def coordinate(cell)
      x = cell % @order
      y = cell / @order
      return x, y
    end

    def col_width
      @col_width ||= @items.max.to_s.size
    end

    def to_s
      @matrix.map! { |e| e ? e : 0}
      @matrix.each_slice(@order) do |arr|
        print "|"
        arr.each do |e|
          print "%#{col_width}d|" % e
        end
        puts
      end
    end
  end

  class Matrix
    attr_accessor :items, :matrix, :order
    include Utils

    def initialize(arg)
      case arg
      when Array then arr = arg
      when Range then arr = arg.to_a
      end

      raise "Not a squre" unless arr.size.square_number?

      @order = Math.sqrt(arr.size).to_i
      @items  = arr
      @matrix = Array.new(@order**2, 0)
    end

    def self.duplicate(arg)
      Marshal.load(Marshal.dump(arg))
    end

    def next_blank_position
      p = matrix.take_while{|i| i != 0}.size
      p != matrix.size ? p : false
    end

    def candidate_numbers(cell)
      left = items - matrix
      x, y = coordinate(cell)
      case
      when x == @order -1
        num = magic_constant - sum_cells(row_indices(y))
        left.include?(num) ? [num] : nil
      when y == @order -1
        num = magic_constant - sum_cells(column_indices(x))
        left.include?(num) ? [num] : nil
      else
        left.select { |i|
          sum_cells(row_indices(y)) + i    <= magic_constant &&
          sum_cells(column_indices(x)) + i <= magic_constant
        }
      end
    end

    def symmetry_constraint_fullfilled?
      if top_left * top_right * buttom_left * buttom_right == 0
        true
      else
        top_left > top_right &&
          top_left > buttom_left &&
          top_left > buttom_right &&
          top_right > buttom_left
      end
    end

    def magic?
      return false unless sum_cells(diagonal_indices1) == magic_constant
      return false unless sum_cells(diagonal_indices2) == magic_constant

      0.upto(@order - 1) do |i|
        if sum_cells(column_indices(i)) != magic_constant ||
          sum_cells(column_indices(i)) != magic_constant
          return false
        end
      end
      true
    end
  end

  class Solver
    def initialize(matrix)
      @matrix = matrix
    end

    def solve
      if @matrix.next_blank_position
        stack = place_a_new_number_in_the_next_blank_cell(@matrix)
        while !stack.empty?
          matrix = Matrix.duplicate(stack.shift)
          Solver.new(matrix).solve
        end
      else
        if @matrix.magic?
          p @matrix if @matrix.magic?
        else
        end
      end
    end

    def place_a_new_number_in_the_next_blank_cell(matrix)
      stack = []
      if cell = matrix.next_blank_position
        nums = matrix.candidate_numbers(cell)
        return stack unless nums
        nums.each do |e|
          new_matrix = Matrix.duplicate(matrix)
          new_matrix.matrix[cell] = e
          stack << new_matrix if new_matrix.symmetry_constraint_fullfilled?
        end
      end
      stack
    end
  end
end

include MagicMatrix

if  __FILE__ == $0
#  m = Matrix.new([17, 113, 47, 89,  59,  29, 71, 5, 101])
  m = Matrix.new([8, 1, 6, 3, 5, 7, 4, 9, 2])
#  m = Matrix.new((1..16))
#  m[0,0] = 1
#  m = Matrix.new((1..9))
  Solver.new(m).solve
  exit
end