Place Non-Attacking Queens
Company: Bytedance
Role: Site Reliability Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Given an integer `n`, return all valid configurations for placing `n` queens on an `n x n` chessboard so that no two queens attack each other.
A queen attacks another queen if they share the same row, column, main diagonal, or anti-diagonal.
Represent each board configuration as a list of `n` strings of length `n`, where `'Q'` represents a queen and `'.'` represents an empty square.
Return the configurations in any order.
Example:
```text
Input: n = 4
Output:
[
[".Q..", "...Q", "Q...", "..Q."],
["..Q.", "Q...", "...Q", ".Q.."]
]
```
Constraints:
```text
1 <= n <= 9
```
After implementing the solution, analyze its time and space complexity.
Quick Answer: This question evaluates a candidate's competency in combinatorial search, constraint reasoning, and algorithmic design for arranging non-attacking pieces on a grid.
Given an integer n, return all valid configurations for placing n queens on an n x n chessboard so that no two queens attack each other.
A queen attacks another queen if they share the same row, column, main diagonal, or anti-diagonal.
Represent each configuration as a list of n strings of length n, where 'Q' represents a queen and '.' represents an empty square.
Return the configurations in any order.
Constraints
- 1 <= n <= 9
- Each configuration must place exactly one queen in every row
- No two queens may share a column, main diagonal, or anti-diagonal
Examples
Input: 1
Expected Output: [["Q"]]
Explanation: On a 1x1 board, the only valid configuration is to place the queen in the single available cell.
Input: 2
Expected Output: []
Explanation: There is no way to place 2 queens on a 2x2 board without them attacking each other.
Hints
- Try placing queens row by row. Once you decide a row, you only need to check whether a column or diagonal is already occupied.
- A cell (row, col) belongs to main diagonal (row - col) and anti-diagonal (row + col). These values can be tracked in sets for O(1) conflict checks.