N-Queens II
N-Queens II 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
Implement totalNQueens to count the distinct ways to place n queens on an n by n chessboard so that no two queens attack one another. Two queens attack one another if they share a row, column, or diagonal.
Every valid arrangement places exactly one queen in each row and each column. Arrangements are distinct when at least one queen occupies a different square.
Return the total number of valid arrangements as an integer. If no arrangement satisfies the rules, return 0.
Example 1:
Input: n = 2 Output: 0 Explanation: With only two rows and two columns, placing one queen in each row forces the queens to share a column or diagonal.
Example 2:
Input: n = 6 Output: 4 Explanation: There are four distinct placements of six queens in which no pair shares a row, column, or diagonal.
Example 3:
Input: n = 7 Output: 40 Explanation: A complete search of the seven-row board produces 40 valid arrangements.
Constraints:
- 1 <= n <= 9 - n is an integer. - The board has n rows and n columns. - The answer fits in a signed 32-bit integer.
Topics and companies
Topics: Backtracking, Recursion, Enumeration.
How to practise N-Queens II on Thita.ai
Starter code is provided in 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!) in the worst case, for the backtracking search. time and O(n) recursion stack space, excluding the integer bit masks. space.
Open N-Queens II in the code editor, or read the N-Queens II editorial for a worked solution with its approach and complexity analysis.
Where N-Queens II 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 II
Other problems that use the same N-Queens / Constraint Satisfaction and Backtracking Patterns techniques:
- Matchsticks to Square — Medium, same subpattern
- N-Queens — 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