Solve the N-Queens problem
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
## Problem
Given an integer **n**, place **n** queens on an **n × n** chessboard so that **no two queens attack each other** (i.e., no two queens share the same row, column, or diagonal).
Return **all distinct valid boards**.
### Input
- An integer `n` (typically `1 ≤ n ≤ 9` in interviews).
### Output
- A list of solutions, where each solution is an array of `n` strings of length `n`.
- Each string contains only:
- `'Q'` for a queen
- `'.'` for an empty cell
### Example
For `n = 4`, one valid output format is:
- `[".Q..","...Q","Q...","..Q."]`
(Your output may list solutions in any order.)
### Notes
- You may assume there is **at most one queen per row** (or per column) in your construction approach.
Quick Answer: This question evaluates a candidate's competence in backtracking, constraint satisfaction, combinatorial search, recursion, and state representation. It is commonly asked in technical interviews because it probes algorithmic problem-solving and handling of combinatorial explosion within the Coding & Algorithms domain, testing both conceptual understanding and practical implementation skills.