=begin
N-Queen Problem

=end

def place_queen(queen_count)
  place(0, queen_count, [])
end

def place(row, queen_count, columns)
  if row == queen_count
    print_queen_place(queen_count, columns)
    return
  end

  movable_cols = get_movable_places(row, queen_count, columns)

  movable_cols.each do |col|
    columns[row] = col

    place(row + 1, queen_count, columns)
  end

end

def get_movable_places(row, queen_count, columns)
  places = []
  
  (0...queen_count).each { |i| places[i] = 1 }

  (0...row).each do |rowidx|
    prev_place = columns[rowidx]

    places[prev_place] = 0

    oppo_angle_left = prev_place - (row - rowidx).abs
    oppo_angle_right = prev_place + (row - rowidx).abs
    
    places[oppo_angle_left] = 0 if oppo_angle_left >= 0
    places[oppo_angle_right] = 0 if oppo_angle_right < queen_count
  end

  movable_cols = []
  places.each_index { |i| movable_cols.push i if 1 == places[i] }

  movable_cols
end

def print_queen_place(queen_count, columns)
  puts "Queen -------------------------------------"

  (0...queen_count).each do |i|
    (0...queen_count).each do |j|
      if j == columns[i]
        print 'Q'
      else
        print '.'
      end
      
    end

    puts
  end
  
end

place_queen(4)