# -*- coding: utf-8 -*-
#
# GAで8-Queenを解く!
#
class Queens
  POPULATION = 1000
  attr_reader :solution

  def randomgene
    (0...8).collect {
      rand(8)
    }
  end

  def initialize
    @genes = []
    POPULATION.times {
      @genes << randomgene
    }
    File.delete("average.log") if File.exist?("average.log")
    File.delete("best.log") if File.exist?("best.log")
  end

  def evaluateone(gene)
    collisions = 0
    v = {}
    (0...8).each { |i|
      collisions += 1 if v[gene[i]]
      v[gene[i]] = ''
    }
    v = {}
    (0...8).each { |i|
      collisions += 1 if v[i+gene[i]]
      v[i+gene[i]] = ''
    }
    v = {}
    (0...8).each { |i|
      collisions += 1 if v[i-gene[i]]
      v[i-gene[i]] = ''
    }
    if collisions == 0 then
      @solution = gene
    end
    # 1.0 / (1.0 + collisions)
    collisions
  end

  def evaluate
    @val = []
    @totalval = 0.0
    totalcollisions = 0.0
    best = 100.0
    (0...POPULATION).each { |i|
      collisions = evaluateone(@genes[i])
      @val[i] = 1.0 / (1.0 + collisions)
      @totalval += @val[i]
      totalcollisions += collisions
      best = collisions if collisions < best
    }
    File.open("average.log","a"){ |f|
      f.puts totalcollisions.to_f / POPULATION
    }
    File.open("best.log","a"){ |f|
      f.puts best.to_f
    }
  end
  
  def selectone
    r = rand(10000) / 10000.0
    v = 0.0
    (0...POPULATION).each { |i|
      if r >= v && r < v + @val[i] / @totalval then
        return @genes[i].dup
      end
      v += @val[i] / @totalval
    }
  end

  def dump
    (0..10).each { |i|
      puts @genes[i].join(' ')
    }
    puts "totalval = #{@totalval}"
  end

  def calc
    newgenes = []
    while newgenes.length < POPULATION do
      if rand(10000) < 6000 then # 交叉
        a = selectone
        b = selectone
        p1 = rand(8)
        p2 = rand(8)
        if p2 < p1 then
          tmp = p2
          p2 = p1
          p1 = tmp
        end
        (p1..p2).each { |i|
          tmp = a[i]
          a[i] = b[i]
          b[i] = tmp
        }
        newgenes << a
        newgenes << b
      elsif rand(10000) < 600 then # 突然変異
        a = selectone
        a[rand(8)] = rand(8)
        newgenes << a
      else
        newgenes << selectone
      end
    end
    @genes = newgenes
  end
end

queens = Queens.new
while true do 
  queens.evaluate
  queens.dump
  queens.calc
  break if queens.solution
end

(0...8).each { |i|
  s = (0...8).collect { '.' }
  s[queens.solution[i]] = 'Q'
  puts s.join(' ')
}