N-Queens
Problem Description
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
Solve it on LeetCode
Approaches
1. Backtracking Approach
The N-Queens problem is a classic problem that can be solved using a backtracking approach. The main idea is to place queens one by one in different rows, starting from the first row. When placing a queen in a particular row, we must ensure that it does not attack any other previously placed queens. For this, we can use three sets to track the columns and two diagonals (positive and negative diagonals).
Intuition:
- Use a recursive function to place queens row by row.
- For each row, try placing the queen in each column and check if it leads to a valid solution.
- Use three sets to track if a queen is already placed in a column, positive diagonal, or negative diagonal.
- If we reach the last row and place all the queens successfully, add the board configuration to the result list.
- Backtrack: If placing a queen in a certain position doesn't lead to a solution, remove the queen (backtrack) and try the next position.
Code:
- Time Complexity: O(N!) - In the worst-case scenario, every queen has N possible options to place.
- Space Complexity: O(N) - Used for storing the sets and board state.
2. Optimized Backtracking with Bitmasking
For an even more optimized approach, we can use bitmasking to manage the columns and diagonals. This reduces the overhead of using sets and improves lookup times to constant.
Intuition:
- Use bitmask integers to represent the columns, positive diagonals, and negative diagonals.
- The idea is similar to the above approach but uses bit manipulation for checking and setting the states of columns and diagonals.
Code:
- Time Complexity: O(N!) - Similar to the traditional approach due to the nature of backtracking.
- Space Complexity: O(N) - Used for storing the board state only as sets are replaced by integers.