We need to place n queens on an n x n chessboard so that no two queens threaten each other. In chess, a queen can attack any piece on the same row, column, or diagonal. So the challenge is finding arrangements where every queen is safe from every other queen.

Since each row can contain at most one queen and we have n queens for n rows, every valid solution must have exactly one queen per row. That transforms the problem from "place n queens anywhere on n^2 squares" into "choose one column for the queen in each row," which is a much smaller search space.

The problem asks us to return all valid configurations, not just count them. This means we need to explore the entire search space and collect every solution we find.

Key Constraints:

Intuition

Since every valid solution has exactly one queen per row, we can represent a solution as a permutation of column indices. For row 0, the queen goes in column perm[0]; for row 1, in column perm[1]; and so on. If we generate all permutations of [0, 1, ..., n-1], each one guarantees no two queens share a row or column. The remaining work is to filter out the permutations where two queens share a diagonal.

This is brute force because we generate all n! permutations first, then check each one. We are not pruning invalid placements early, so we waste time exploring permutations that have diagonal conflicts in the first few rows.

Algorithm

Example Walkthrough

Input: n = 4

Permutation [0,1,2,3]: queens on the main diagonal, rows 0 and 1 share a diagonal. INVALID.

Permutation [1,3,0,2]: check all pairs, no diagonal conflicts. VALID! Board: [".Q..","...Q","Q...","..Q."]

Permutation [2,0,3,1]: check all pairs, no diagonal conflicts. VALID! Board: ["..Q.","Q...","...Q",".Q.."]

Result: 2 valid solutions found out of 4! = 24 total permutations.

Code

The bottleneck is generating every permutation in full before checking for diagonal conflicts. The next approach checks conflicts as each queen is placed and abandons a partial placement the moment it violates a constraint.

Intuition

Instead of generating all permutations and filtering afterward, we place queens one row at a time and check for conflicts immediately. If placing a queen in a particular column conflicts with any previously placed queen, we skip that column entirely. This is backtracking: extend a partial solution, detect failure early, and abandon dead ends before exploring them.

The conflict check needs to be fast. A queen at position (row, col) attacks its column, its main diagonal, and its anti-diagonal. All squares on the same main diagonal share the same value of (row - col), and all squares on the same anti-diagonal share the same value of (row + col). So we maintain three sets, one for occupied columns, one for occupied diagonals (row - col), and one for occupied anti-diagonals (row + col), which turns each conflict check into three O(1) lookups instead of a scan over every placed queen.

Algorithm

Example Walkthrough

Code

Each conflict check in the set approach still involves three hash lookups per candidate column. The next approach replaces the sets with integer bitmasks, so a few bitwise operations compute all available columns for a row at once.

Intuition

The algorithm is the same as Approach 2: place queens row by row and prune on conflicts. The difference is the data structure. Instead of hash sets, we use integers as bitmasks to track which columns and diagonals are under attack. A single integer represents all n columns, where bit i set to 1 means column i is occupied.

The diagonals are handled by shifting. When we move from row r to row r+1, every existing main-diagonal threat advances one column to the right, and every anti-diagonal threat advances one column to the left. So we carry the diagonal bitmasks down the recursion with a left shift for diags and a right shift for antiDiags. At each row, ORing the column mask with the two shifted diagonal masks gives every unsafe column, and the complement gives every available column in a single integer.

Algorithm

Example Walkthrough

Code