N-Queens

N-Queens is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the N-Queens / Constraint Satisfaction subpattern.

Problem statement

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1 Output: [["Q"]]

Constraints:

- 1 <= n <= 9

Topics and companies

Topics: Array, Backtracking.

Reported in interviews at Facebook, Microsoft, Amazon, ByteDance, Apple, Adobe.

How to practise N-Queens on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N!) — For each column, we try all N rows, but due to constraints (no two queens in the same row/diagonal), the number of valid placements is much less than N^N. The total number of solutions is bounded by O(N!), as each queen must be placed in a unique row and column. time and O(N^2) — The recursion stack can go up to O(N) depth, and each board configuration is O(N^2) in size. The result vector can store up to O(N!) solutions, each of size O(N^2), but for a single solution, the auxiliary space is O(N^2). space.

Open N-Queens in the code editor, or read the N-Queens editorial for a worked solution with its approach and complexity analysis.

Where N-Queens sits in the DSA pattern sheet

• Backtracking Patterns pattern guide
• N-Queens / Constraint Satisfaction subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to N-Queens

Other problems that use the same N-Queens / Constraint Satisfaction and Backtracking Patterns techniques:

• Sudoku Solver — Hard, same subpattern
• Check if Word Can Be Placed In Crossword — Medium, same pattern
• Combinations — Medium, same pattern
• Combination Sum — Medium, same pattern
• Combination Sum II — Medium, same pattern
• Generate Parentheses — Medium, same pattern