Katkat
Back

Place Non-Attacking Queens

ByteDanceSite Reliability Engineer · Technical Screen
HardSite Reliability EngineerTechnical ScreenCoding & Algorithms

Last updated

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.