51. N-Queens
N-Queens (LeetCode 51) 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.
How to solve N-Queens
N-Queens is a N-Queens and Constraint Satisfaction problem, part of Backtracking Patterns. Solve N-Queens and Sudoku using backtracking with constraint propagation.
Work towards the solution in these steps:
- Consider using backtracking to explore all possible placements of queens row by row, ensuring at each step that the current placement doesn't violate the constraints.
- To efficiently check if a queen can be placed, track columns and diagonals that are already occupied by previously placed queens instead of scanning the entire board every time.
- Remember that the diagonals can be identified by the sums and differences of row and column indices, which allows constant-time checks for conflicts.
The reference solution runs in O(N!) time and O(N^2) space.
The N-Queens solution and editorial walks through the full approach with reference code.
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!) time and 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
Problems related to N-Queens
Other problems that use the same N-Queens / Constraint Satisfaction and Backtracking Patterns techniques:
- Matchsticks to Square — Medium, same subpattern
- N-Queens II — Hard, same subpattern
- 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
N-Queens FAQ
What is the LeetCode number of N-Queens?
N-Queens is LeetCode problem 51, rated Hard.
What pattern is used to solve N-Queens?
N-Queens is a N-Queens and Constraint Satisfaction problem. It belongs to the Backtracking Patterns pattern, in the N-Queens / Constraint Satisfaction subpattern.
What is the time complexity of N-Queens?
The reference solution runs in O(N!) time and O(N^2) space.
Which companies ask N-Queens?
N-Queens has been reported in interviews at Facebook, Microsoft, Amazon, ByteDance, Apple, Adobe.