n-queens.rb

# @param {Integer} n
# @return {String[][]}
def build_board(n, placed_queens)
  board = Array.new
  0.upto(n-1) { |row|
    row_str = ""
    0.upto(n-1) { |col|
      if (placed_queens.include?(row*n + col))
        row_str += "Q"
      else
        row_str += "."
      end
    }
    board.push(row_str)
  }
  return board
end

def space_collides(n, space, placed_queens)
  row = space / n
  col = space % n
  placed_queens.each { |queen_space|
    queen_row = queen_space / n
    queen_col = queen_space % n
    return true if (queen_row == row)
    return true if (queen_col == col)
    return true if ((queen_row - row).abs == (queen_col - col).abs)
  }
  return false
end

def find_open_space(n, space, placed_queens)
  space.upto(n**2 - 1) { |test_space|
    return test_space unless space_collides(n, test_space, placed_queens)
  }
  return false
end

def search_n_queens(n, space, placed_queens, solutions)
  if (n == placed_queens.length)
    solutions.push(placed_queens)
    return
  end
  return if (space > n**2 - 1)
  while (space = find_open_space(n, space, placed_queens))
    search_n_queens(n, space + 1, placed_queens + [space], solutions)
    space += 1
  end
end

def solve_n_queens(n)
  solutions = Array.new
  search_n_queens(n, 0, Array.new, solutions)
  return solutions.map {|solution| build_board(n, solution)}
end

solve_n_queens(4).each { |board|
  puts board
  puts ""
}