# -*- 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(' ')
}