module Rudoku # namespace power!
  class Sudoku
    attr_reader :fields
    attr_accessor :changed

    def initialize
      @fields = Array.new(9 * 9) do |i|
        x = i % 9
        y = i / 9
        Field.new(self, x, y)
      end
      @changed = false
    end

    def self.from_str(str)
      return if str.length != 81
      s = new
      (0..80).each do |i|
        s[i] = str[i].chr.to_i unless %w(_ x - 0).include? str[i].chr
      end
      s.changed = false
      return s
    end

    def [](*val) # 1-based
      if val.size == 2 # 2, 3
        x = val[0] - 1
        y = val[1] - 1
      elsif val.size == 1 # B3
        if val[0].kind_of? Integer
          x = val[0] % 9
          y = val[0] / 9
        else
          str = val[0].to_s
          x = str[0] - ?A
          y = str[1] - ?1
        end
      else
        return nil
      end

      @fields[x + y * 9]
    end

    def []=(i, number) # also allows setting of multiple values: s[:B5] = [1, 2, 5]
      self[i].value = number
    end

    def solved?
      @fields.all? { |f| f.solved? } && consistent?
    end

    def changed?
      @changed
    end

    def consistent?
      # This check will be run on an unsolved sudoku!
      # The result should be meaningful either way.

      consistency_test = proc do |group|
        found_values = []
        (0..8).each do |i|
          v = group[i].value
          unless v.nil?
            return false if found_values.include?(v)
            found_values << v
          end
        end
      end

      each_row(&consistency_test)
      each_column(&consistency_test)
      each_square(&consistency_test)

      return true
    end

    def to_s
      row_strings = (1..9).collect { |i| row_to_s(i) }
      row_strings.join("\n-+-+-+-+-+-+-+-+-\n")
    end

    def row(i) # 1-based
      @fields[(9 * (i - 1))..(9 * (i - 1) + 8)]
    end

    def column(i) # 1-based
      @fields.values_at(*(0..8).collect{ |j| 9 * j + i - 1})
    end

    def square(i) # 1-based
      gx = (i - 1) % 3
      gy = (i - 1) / 3
      fs = []
      (0..2).each do |j|
        fs += @fields[(27*gy + 3*gx + 9*j)..(27*gy + 3*gx +9*j + 2)]
      end
      fs
    end

    def row_to_s(i)
      (row(i).collect { |f| f.to_s }).join("|")
    end

    def containing_square(i, j) # 1-based
      gx = (i - 1) / 3
      gy = (j - 1) / 3
      square(gx + 3*gy + 1)
    end

    def each_row
      (1..9).each { |i| yield row(i) }
    end

    def each_column
      (1..9).each { |i| yield column(i) }
    end

    def each_square
      (1..9).each { |i| yield square(i) }
    end

    def each_field
      (0..80).each { |i| yield self[i] }
    end


    def count_empty
      count = 0
      each_field { |f| count += 1 unless f.solved? }
      count
    end


    def best_force_candidate # find an empty field with the least possibilities
      return nil if solved?

      best_candidate = nil
      best_count = 10 # 1 more than the maximum

      each_field do |f|
        next if f.solved?

        if f.possibilities.size < best_count
          best_candidate = f
          best_count = f.possibilities.size
        end
      end

      best_candidate
    end


    def copy_data(source)
      @changed = source.changed
      source.each_field do |f|
        self[f.position].set_possibilities(f.possibilities)
      end
    end
  end

  class Field
    attr_reader :possibilities, :x, :y, :sudoku

    def initialize(sudoku, x, y)
      @sudoku = sudoku
      @possibilities = (1..9).to_a
      @x = x
      @y = y
    end

    def remove(numbers)
      numbers = [*numbers] # this works for a single number and for ranges, too
      new_possibilities = @possibilities - numbers

      if new_possibilities == @possibilities # no change
        return false
      elsif new_possibilities.size >= 1
        @possibilities = new_possibilities
        @sudoku.changed = true
        return true
      else
        return false # no change
      end
    end

    def set_possibilities(p) # achterpoortje voor de bruteforcer (moet possibilities kunnen resetten)
      @possibilities = [*p].uniq
    end

    def position
      (?A + x).chr + (y + 1).to_s # 2, 3 => B3
    end

    def solved?
      @possibilities.size == 1
    end

    def value
      solved? ? @possibilities[0] : nil
    end

    def value=(number)
      remove((1..9).to_a - [*number])
    end

    def to_s
      solved? ? value.to_s : " "
    end
  end

  class Rule
    attr_reader :salience, :name

    def initialize(name = nil, salience = 0, &block)
      @name = name
      @salience = salience
      @logic = block
    end

    def apply_to(sudoku)
      args_iterate(@logic.arity - 1) do |*args|
        info = "#{name} (#{args.join(',')})"
        @logic.call(sudoku, *args)
        # puts success ? "APPLIED #{info}" : "SKIPPED #{info}"
        puts "APPLIED #{info}" if sudoku.changed?

        sudoku.changed?
      end
    end

    protected
      def args_iterate(n) # n: number of arguments
        if n == 0
          yield
        else
          # fill in leftmost parameter, iterate over the remaining argumnents
          args_iterate(n - 1) do |*args|
            ret = false
            (1..9).each do |i|
              ret = yield(i, *args)
              break if ret # breaks out of all
            end

            ret # return value has to be passed on to the higher level
          end
        end
      end
  end

  class Solver
    attr_reader :rules
    attr_reader :ara_count, :sra_count, :guess_count, :cg_count # stats

    def initialize(rules = [])
      @rules = rules
    end

    def sort_rules
      @rules = @rules.sort_by { |r| r.salience }.reverse # highest salience first
    end

    def solve(sudoku, do_force = false)
      @ara_count = 0
      @sra_count = 0
      @guess_count = 0
      @cg_count = 0
      # if apply_rules returns true, no bruteforcing is required.
      if do_force
        solve_with_force(sudoku)
      else
        apply_rules(sudoku)
      end
    end

    def solve_with_force(sudoku)
      return true if apply_rules(sudoku)
      return false unless sudoku.consistent? # applying the rules may have made the sudoku inconsistent. bubble up!

      guess_and_solve(sudoku) ? sudoku.solved? : false
    end

    def guess_and_solve(sudoku)
      backup = Sudoku.new
      backup.copy_data(sudoku)

      field = sudoku.best_force_candidate
      possibilities = field.possibilities

      trial_value = possibilities.first
      field.value = trial_value
      @guess_count += 1
      @cg_count += 1

      puts "GUESSING #{field.position} = #{trial_value}"

      # safety, might be obsolete, I dunno.
      return true if sudoku.solved?

      success = solve_with_force(sudoku) # recursion, backtracking
      if success
        return true
      else
        # guess lead to inconsistency =>
        @cg_count -= 1 # guess wasn't correct after all!
        sudoku.copy_data(backup) # restore values
        field.set_possibilities(possibilities - [trial_value])
        return solve_with_force(sudoku) # try solving again, there's more info now (one less possibility!)
      end
    end

    def apply_rules(sudoku)
      sort_rules

      # iterate over all implemented rules in order of saliency
      # if one is applicable and changes the sudoku, start over
      @rules.each do |rule|
        rule.apply_to(sudoku)
        @ara_count += 1

        if sudoku.changed?  # something has changed -> restart rule application
          sudoku.changed = false
          @sra_count += 1
          retry
        end
      end

      return sudoku.solved?
    end
  end


  def others(j)
    ([*(1..9)] - [j]).each { |i| yield i }
  end
end



include Rudoku



#################### REGELS ####################
# hebben een aantal parameters, de eerste is het sudoku-object, de andere lopen telkens van 1 tot 9

# BASISREGELS: enkelvoudige propagatie
row_rule = Rule.new "row elimination", 100 do |sudoku, i, j|
  if sudoku[i,j].solved? # when a solved field occurs, remove its value from all other fields on the same row
    others(j) { |k| sudoku[i, k].remove(sudoku[i, j].value) } # iterate over columns, remove value
  end
end

column_rule = Rule.new "column elimination", 90 do |sudoku, i, j|
  if sudoku[i, j].solved? # when a solved field occurs, remove its value from all other fields on the same column
    others(i) { |k| sudoku[k, j].remove(sudoku[i, j].value) } # iterate over rows, remove value
  end
end

square_rule = Rule.new "square elimination", 80 do |sudoku, i, j|
  if sudoku[i, j].solved?
    square = sudoku.containing_square(i, j)
    square_index = ((i - 1) % 3) + 3 * ((j - 1) % 3)
    others(square_index) { |k| square[k - 1].remove(sudoku[i, j].value) }
  end
end


#################### TEST ####################
metro = "--38----4-7--5461-2----7-5-9-532-7------8593-6--49----7--6---8--26-1----4-----1-2"
manna_symmetrisch = "7-42-13-5---------3--5-7--26-5---8-3----7----4-3---9-72--9-5--1---------5-97-36-4"
manna_tiseenacht = "2--81--46---6--1--1-7----2-------261-2-9-3-5-654-------1----6-4--3--6---48--79--5"

# su = Sudoku.from_str(manna_symmetrisch)
su = Sudoku.new # leeg!

puts su.to_s
puts "Empty fields: #{su.count_empty}"
puts "Consistent: #{su.consistent?}"

puts "\n\n>> Solving now...\n"
bruteSolver = Solver.new # empty ruleset -> bruteforce
stupidSolver = Solver.new [row_rule, column_rule, square_rule]

so = stupidSolver

so.solve(su, true)

puts "\n\n" + su.to_s + "\n\n"
puts "Empty fields: #{su.count_empty}"
puts "Consistent: #{su.consistent?}"
puts "\n\n>> SOLVED!" if su.solved?
puts "#{so.ara_count} attempted rule applications"
puts "#{so.sra_count} succesful rule applications"
puts "#{so.guess_count} attempted guesses"
puts "#{so.cg_count} correct guesses"