N-Queens — Hard Coding Interview Question

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Return all distinct solutions to the n-queens puzzle.

Example

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Constraints

• 1 ≤ n ≤ 9

Topics & Companies

Topics: backtracking

Asked by: Amazon, Google, Meta, Microsoft, Apple

Optimal Solution Complexity

Time complexity: O(n!). Space complexity: O(n²).

Practice more

• All DSA Problems
• DSA Patterns