cswork / libraryOpen practice workspace

Coding questions · ByteDance

Place Non-Attacking Queens

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 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:

Input: n = 4
Output:
[
  [".Q..", "...Q", "Q...", "..Q."],
  ["..Q.", "Q...", "...Q", ".Q.."]
]

Constraints:

1 <= n <= 9

After implementing the solution, analyze its time and space complexity.

Place Non-Attacking Queens

Hints

  1. Try placing queens row by row. Once you decide a row, you only need to check whether a column or diagonal is already occupied.
  2. 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.