n-queens.rb

# @param {Integer} n
# @return {String[][]}
def solve_n_queens(n)
  return [] if n <= 0

  result = []
  initial_board = Array.new(n) { Array.new(n) { '.' } }
  backtrack(n, initial_board, result)
  result
end

def backtrack(n, candidate, result, row=0, cols=Set.new, diag1=Set.new, diag2=Set.new)
  if row == n
    result << candidate.map { |r| r * '' }.clone
    return result
  end

  (0...n).each do |col|
    next if cols.include?(col)
    next if diag1.include?(row+col)
    next if diag2.include?(row-col)

    cols.add(col)
    diag1.add(row+col)
    diag2.add(row-col)
    candidate[row][col] = 'Q'

    backtrack(n, candidate, result, row+1, cols, diag1, diag2)

    candidate[row][col] = '.'
    diag2.delete(row-col)
    diag1.delete(row+col)
    cols.delete(col)
  end
end