n-queens.rb

require 'set'

def build_board(n, queens)
  board = Array.new(n) { "." * n }
  queens.each { |spot|
    board[spot / n][spot % n] = "Q"
  }
  return board
end

def search_n_queens(n, space, sets, queens, solutions)
  if (n == queens.length)
    solutions.push(queens)
    return
  end

  while (space < n**2)
    row = space / n
    col = space % n
    space += 1
    next if (sets['rows'].include?(row))
    next if (sets['cols'].include?(col))
    next if (sets['hills'].include?(row + col))
    next if (sets['dales'].include?(row - col))
    sets['rows'].add(row)
    sets['cols'].add(col)
    sets['hills'].add(row + col)
    sets['dales'].add(row - col)
    search_n_queens(n, space, sets, queens + [space-1], solutions)
    sets['rows'].delete(row)
    sets['cols'].delete(col)
    sets['hills'].delete(row + col)
    sets['dales'].delete(row - col)
  end
end

def solve_n_queens(n)
  solutions = Array.new
  sets = {
    'rows' => Set.new,
    'cols' => Set.new,
    'hills' => Set.new,
    'dales' => Set.new
  }
  search_n_queens(n, 0, sets, Array.new, solutions)
  return solutions.map {|solution| build_board(n, solution)}
end