#!/usr/bin/env ruby
 
# Desk info:
# 0,7 1,7 ... 7,7
# ... ... ... ...
# 0,1 1,1 ... 7,1
# 0,0 1,0 ... 7,0
SIZE = 8
 
# finished example: 6 3 1 4 7 0 2 5
 
class VariantList
 
	attr_accessor :validator
	attr_accessor :list
 
	def initialize
		@validator = [ ]
		@list = [ ]
	end
 
	def size?
		return list.size
	end
 
	def add(t)
		@list << t
		worker = @validator
		t.each do|i|
			worker[i] = [] if worker[i] == nil
			worker = worker[i]
		end
		# TODO: implement second attribute with
		#       a) conflict counts
		#       b) conflicts sum
		#       to allow: worker << [information about variant]
	end
 
	def include?(t)
		worker = @validator
		t.each do|i|
			return false if worker[i] == nil
			worker = worker[i]
		end
		return true if worker.class == Array && worker.size == 0
		return false
	end
 
	def info()
		print 'Found ', @list.size, ' variants total.', "\n"
	end
 
end
 
class Board
 
	attr_accessor :members
 
	def initialize
		@members = [ ]
	end
 
	def <<(m)
		@members << m
	end
 
	def variant
		r = [ ]
		@members.each{|m| r << m.y }
		return r
	end
 
	def in_conflict?(q1, q2)
		diff = q1.x - q2.x
		return (q1.x == q2.x || q1.y == q2.y || q1.y == q2.y+diff || q1.y == q2.y-diff)
	end
 
	def field_conflicts?(x, y)
		pseudo = Queen.pseudo(x,y)
		return conflicts?(pseudo)-1
	end
 
	def conflicts?(queen)
		sum = 0
		@members.each{|m|
			next if m == queen
			sum += 1 if in_conflict?(queen, m)
		}
		return sum
	end
 
	def finished?
		@members.each{|m| return false if conflicts?(m) != 0 }
		true
	end
 
	def draw
		line  = '.'
		2.upto(SIZE){ line += " ." }
		line += "\n"
		out = ''
		1.upto(SIZE){ out += line }
 
		members.each{|m|
#			m.info()
			out[ SIZE*SIZE*2 - SIZE*m.y*2 - SIZE*2 + m.x*2 ] = conflicts?(m).to_s #'@'
		}
		print out
	end
 
end
 
class Queen
 
	attr_accessor :x
	attr_accessor :y
 
	def initialize(x)
		@x = x
		@y = (rand*255).to_i % SIZE
	end
 
	def self.pseudo(x, y)
		q = Queen.new(x)
		q.y = y
		return q
	end
 
	def name
		pos = axis2pos(@x, @y)
		return "D" + pos[0] + pos[1].to_s
	end
 
end
 
def axis2pos(x,y)
	s = 'a'
	s[0] = ?a + x
	y += 1
	return [s, y]
end
 
STDOUT.sync = true
begin
 
	# Initialize
	variants = VariantList.new
	board = Board.new
	0.upto(SIZE-1){|w| board << Queen.new(w) }
	if ARGV.size > 0 then
		board.members.each_with_index{|m,i|
			m.y = ARGV[i].to_i
		}
	end
	variants.add(board.variant())
 
	puts 'Initial board:'
	board.draw()
	puts
 
	#Start processing
	puts 'Processing...'
 
	while (!board.finished?) do
		if variants.size? % 1 == 0 then
			print ". "
			print variants.size?, "\n" if variants.size? % 35 == 0
		end
 
		# Put figures in order of conflicts number
		order = [ ]
		0.upto(SIZE-1){|i| order[i] = [ ] }
 
		board.members.each{|m|
			order[board.conflicts?(m)] << m
		}
 
		# Walk-through in reverse order to eliminate bad ones first
		changed = false
		order.reverse.each_with_index{|o,oi|
			next if o.size == 0
			break if changed
			o.each{|m|
				break if changed
#				print 'Examining member [', m.x, ',', m.y, '] with conflict rate ', SIZE-1-oi, "...\n"
 
				# Put fields in row in order of conflicts with other figures
				positions = [ ]
				0.upto(SIZE-1){|y|
					confs = board.field_conflicts?(m.x, y)
					positions[confs] = [ ] if positions[confs] == nil
					positions[confs] << y if y != m.y
				}
 
				# Walk through fields, starting with least conflicting first
				positions.each_with_index{|c,ci|
					break if changed
					next if c == nil
					c.each{|f|
#						next if ci > oi # TODO: Why does this i-loops 7-6-5-...-0 start tile?
#						print 'Examining field with conflict rate ', ci, "...\n"
						# check whether moving member here isn't in variants already
						current = board.variant()
						current[m.x] = f
						break if variants.include?(current)
						# move figure
						m.y = f
						changed = true
#						print 'New board ', variants.size?, ":\n"
#						board.draw()
						variants.add(current)
						break
					}
				}
 
			}
		}
 
	end
 
	# Board is now in finished state
	print "[done!]\n\n"
	print "Task finished in ", variants.size?-1, " steps.\n"
	puts 'Finished board:'
	board.draw()
	puts
 
end