N Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard so that no two queens can attack each other.

A queen in a chessboard can attack horizontally, vertically, and diagonally.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a unique board layout where the queen pieces are placed. 'Q' indicates a queen and '.' indicates an empty space. You may return the answer in any order.

Examples

• 1 ≤ n ≤ 8

Prerequisites

Before attempting this problem, you should be comfortable with:

• Backtracking - Understanding how to explore all possibilities by making choices and undoing them when they lead to invalid states
• Recursion - The solution builds the board row by row using recursive calls
• 2D Arrays/Matrices - Working with board representations and understanding coordinate systems
• Diagonal Patterns - Recognizing that cells on the same diagonal share the property (row + col) or (row - col)

1. Standard Backtracking

Intuition

The goal is to place one queen in each row such that no two queens attack each other.

Key observations:

• A queen can attack vertically, diagonally left, and diagonally right
• Since we place queens row by row from top to bottom, we only need to check rows above the current row
• If a position is safe, we place a queen and move to the next row
• If we reach a dead end, we backtrack by removing the last queen and trying another column

This is a classic backtracking + constraint checking problem.

Create an empty n x n board filled with ".". Start backtracking from row 0. For the current r (row): Try placing a queen in every c (column). Before placing, check if the position is isSafe: - No queen in the same column above - No queen in the upper-left diagonal - No queen in the upper-right diagonal If safe: Place the queen ("Q") Recurse to the next row Remove the queen after returning (backtrack) If all n rows are filled: Convert the board into a list of strings and store it as one valid solution Continue until all possibilities are explored.

2. Backtracking (Hash Set)

Intuition

Instead of checking the board every time to see if a queen is safe, we remember the attacked positions using hash sets.

For any queen at position (row, col):

• Column conflict → same col
• Positive diagonal conflict → same row + col
• Negative diagonal conflict → same row - col

By storing these in sets, we can check whether a position is safe in O(1) time. We still place one queen per row, move row by row, and backtrack when a placement leads to a conflict.

Use three hash sets: col → tracks used c (columns) posDiag → tracks (row + col) negDiag → tracks (row - col) Initialize an empty n x n board with ".". Start backtracking from row 0. For the current r (row): Try every c (column) If c, (r + c), or (r - c) is already in the sets → skip If safe: Add c, (r + c), (r - c) to the sets Place "Q" on the board Recurse to the next row If all rows are filled: Convert the board into a list of strings and save it Backtrack: Remove the queen from the board Remove entries from all sets Continue until all valid configurations are found.

Time Complexity: O(N!) because we place one queen per row, with roughly N options for the first, N-2 for the second, etc.

Space Complexity: O(N²) for the board state and recursion stack.

Common Pitfalls

Checking Only Columns and Forgetting Diagonals

A frequent mistake is checking only whether a column is occupied while neglecting diagonal conflicts. Queens attack along both diagonals, so you must verify the upper-left diagonal (where row - col is constant) and the upper-right diagonal (where row + col is constant). Missing either diagonal check will produce invalid board configurations.

Forgetting to Backtrack State

After recursively exploring a placement and returning, you must undo the state changes (remove the queen from sets/arrays and reset the board position to "."). Failing to properly backtrack leaves stale state that incorrectly blocks future valid placements.

Not Creating a Deep Copy of the Board When Saving Solutions

When a valid configuration is found, you must create a copy of the board before adding it to the results. Simply appending a reference to the same board object means all stored solutions will reflect subsequent modifications during backtracking.

# Wrong: appends a reference to the mutable board res.append(board) # Correct: creates a copy of the board copy = ["".join(row) for row in board] res.append(copy)