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. This observation is crucial because it transforms the problem from "place n queens anywhere on n^2 squares" into "choose one column for the queen in each row." That 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. We just need to filter out the permutations where 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 before checking for diagonal conflicts. What if we checked for conflicts as we placed each queen and stopped exploring the moment we detected a violation?

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 creates a conflict with any previously placed queen, we skip that column entirely. This is the essence of backtracking: explore, detect failure early, and prune.

The key insight is how to check conflicts efficiently. A queen at position (row, col) attacks three things: its column, its main diagonal, and its anti-diagonal. Here is the trick: 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 can maintain three sets, one for occupied columns, one for occupied diagonals (row - col), and one for occupied anti-diagonals (row + col), and check membership in O(1).

Algorithm

Example Walkthrough

Code

The hash set approach is already excellent, but each conflict check involves three hash set lookups. What if we could replace those with a single bitwise operation that tells us all available columns at once?

Intuition

The idea is the same as Approach 2: place queens row by row, prune on conflicts. But instead of hash sets, we use integers as bitmasks to track which columns and diagonals are under attack. A single integer can represent all n columns, where bit i being 1 means column i is occupied.

The clever part is how diagonals shift. When we move from row r to row r+1, a queen's main diagonal attack shifts one column to the right, and its anti-diagonal attack shifts one column to the left. So at each row, we shift the diagonal bitmasks accordingly and OR them together with the column bitmask. The result tells us exactly which columns are unsafe, and its complement tells us which columns are available, all in O(1).

Algorithm

Example Walkthrough

Code