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 <= 9The N-Queens problem asks you to place N queens on an N x N chessboard so that no two queens attack each other. The most effective strategy is backtracking, where you place queens row by row while ensuring that the current placement does not conflict with previous ones.
At each row, try placing a queen in every column and check whether the column, main diagonal, or anti-diagonal is already occupied. Using data structures such as sets or boolean arrays to track used columns and diagonals helps perform these checks efficiently. If a placement is valid, continue recursively to the next row; otherwise, backtrack and try another position.
This systematic exploration prunes invalid configurations early, significantly reducing the search space. While the worst-case search is large, pruning ensures practical performance for typical constraints.
The typical time complexity is around O(N!) due to the branching possibilities, while the extra space mainly comes from recursion and tracking structures.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with column and diagonal tracking | O(N!) | O(N) |
| Backtracking with bitmask optimization | O(N!) | O(N) |
Abdul Bari
This approach involves using backtracking to place queens row by row, exploring valid positions recursively. Each queen placement is validated based on column and diagonal restrictions. If a valid placement is found, the algorithm progresses to the next row, otherwise it backtracks and attempts alternative placements.
Time Complexity: O(N!), because we are trying N possible positions for each row for N queens.
Space Complexity: O(N^2), due to the storage of the board states and recursion stack.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5bool isValid(int row, int col, int*
This C solution uses a backtracking approach to place queens row by row, ensuring each placement is valid by checking current column and diagonal conflicts. The recursive function solve advances to next row if a queen is placed, or backtracks if a conflict arises. Valid solutions are stored in a dynamically resized list of boards.
This approach optimizes the placement verification using bit manipulation, reducing the auxiliary space by managing columns and diagonals in integer bitmasks. This permits efficient bitwise operations for placing queens and checking potential attacks.
Time Complexity: O(N!), each row considers N placements, simplified by binary check.
Space Complexity: O(N), due to condensed state tracking via differential lists.
1from typing import List
2
3def solveNQueens(
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, bitmasking can be used to represent columns and diagonals more efficiently. This reduces overhead from data structures and allows faster conflict checks, which is especially helpful for larger board sizes.
Yes, N-Queens is a classic backtracking problem frequently discussed in technical interviews, including FAANG-style interviews. It tests recursion, constraint checking, and pruning strategies.
The optimal approach uses backtracking. You place queens row by row while tracking used columns and diagonals to avoid conflicts. This allows early pruning of invalid placements and efficiently explores valid board configurations.
Common implementations use sets or boolean arrays to track occupied columns, main diagonals, and anti-diagonals. These structures allow constant-time checks to determine whether placing a queen is safe.
This Python implementation enhances the typical backtracking with bit positioning. The current column and diagonals are represented with list-formed negative and positive differential tracking to accommodate queen positions and check constraints efficiently.