51. N Queens - Explanation

Description

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.

Example 1:

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Explanation: There are two different solutions to the 4-queens puzzle.

Example 2:

Input: n = 1

Output: [["Q"]]

Constraints:

1 <= n <= 8

Recommended Time & Space Complexity

You should aim for a solution with O(n!) time and O(n^2) space, where n is the size of the given square board.

Hint 1

A queen can move in 8 directions, and no two queens can be in the same row or column. This means we can place one queen per row or column. We iterate column-wise and try to place a queen in each column while ensuring no other queen exists in the same row, left diagonal, or left bottom diagonal. Can you think of a recursive algorithm to find all possible combinations?

Hint 2

We can use backtracking to traverse through the columns with index c while maintaining a board that represents the current state in the recursive path. We reach the base condition when c == n and we add a copy of the board to the result. How would you implement this?

Hint 3

We initialize an empty board and recursively go through each column. For each column, we check each cell to see if we can place a queen there. We use a function to check if the cell is suitable by iterating along the left directions and verifying if the same row, left diagonal, or left bottom diagonal are free. If it is possible, we place the queen on the board, move along the recursive path, and then backtrack by removing the queen to continue to the next cell in the column.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. 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.

Algorithm

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.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        board = [["."] * n for i in range(n)]

        def backtrack(r):
            if r == n:
                copy = ["".join(row) for row in board]
                res.append(copy)
                return
            for c in range(n):
                if self.isSafe(r, c, board):
                    board[r][c] = "Q"
                    backtrack(r + 1)
                    board[r][c] = "."

        backtrack(0)
        return res

    def isSafe(self, r: int, c: int, board):
        row = r - 1
        while row >= 0:
            if board[row][c] == "Q":
                return False
            row -= 1

        row, col = r - 1, c - 1
        while row >= 0 and col >= 0:
            if board[row][col] == "Q":
                return False
            row -= 1
            col -= 1

        row, col = r - 1, c + 1
        while row >= 0 and col < len(board):
            if board[row][col] == "Q":
                return False
            row -= 1
            col += 1
        return True

Time & Space Complexity

Time complexity: $O(n!)$
Space complexity: $O(n ^ 2)$

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.

Algorithm

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.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = set()
        posDiag = set()
        negDiag = set()

        res = []
        board = [["."] * n for i in range(n)]

        def backtrack(r):
            if r == n:
                copy = ["".join(row) for row in board]
                res.append(copy)
                return

            for c in range(n):
                if c in col or (r + c) in posDiag or (r - c) in negDiag:
                    continue

                col.add(c)
                posDiag.add(r + c)
                negDiag.add(r - c)
                board[r][c] = "Q"

                backtrack(r + 1)

                col.remove(c)
                posDiag.remove(r + c)
                negDiag.remove(r - c)
                board[r][c] = "."

        backtrack(0)
        return res

Time & Space Complexity

Time complexity: $O(n!)$
Space complexity: $O(n ^ 2)$

3. Backtracking (Visited Array)

Intuition

This approach is the array-based version of the hash-set solution.

Instead of using sets, we use boolean arrays to mark whether a column or diagonal is already occupied by a queen.
This works because:

Columns are limited to n
Diagonals can be mapped to indices using math

For a queen at position (row, col):

Column index → col
Positive diagonal ( / ) → row + col
Negative diagonal ( \ ) → row - col + n (shifted to avoid negative index)

If any of these positions are already marked True, placing a queen there would cause a conflict.

We place queens row by row, and backtrack when no safe column is available.

Algorithm

Create three boolean arrays:
- col[n] → tracks occupied columns
- posDiag[2n] → tracks row + col
- negDiag[2n] → tracks row - col + n
Initialize an empty n x n board filled with ".".
Start backtracking from row 0.
For the current r (row):
- Try every c (column)
- If col[c], posDiag[r+c], or negDiag[r-c+n] is true, skip
If safe:
- Mark col[c], posDiag[r+c], negDiag[r-c+n] as true
- Place "Q" on the board at (r, c)
- Recurse to row r + 1
If r == n:
- Convert the board to strings and store the solution
Backtrack:
- Remove the queen
- Reset the corresponding boolean entries
Continue until all valid boards are generated.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = [False] * n
        posDiag = [False] * (n * 2)
        negDiag = [False] * (n * 2)
        res = []
        board = [["."] * n for i in range(n)]

        def backtrack(r):
            if r == n:
                copy = ["".join(row) for row in board]
                res.append(copy)
                return
            for c in range(n):
                if col[c] or posDiag[r + c] or negDiag[r - c + n]:
                    continue
                col[c] = True
                posDiag[r + c] = True
                negDiag[r - c + n] = True
                board[r][c] = "Q"

                backtrack(r + 1)

                col[c] = False
                posDiag[r + c] = False
                negDiag[r - c + n] = False
                board[r][c] = "."

        backtrack(0)
        return res

Time & Space Complexity

Time complexity: $O(n!)$
Space complexity: $O(n ^ 2)$

4. Backtracking (Bit Mask)

Intuition

This is the most optimized backtracking approach for the N-Queens problem.

Instead of using arrays or hash sets to track occupied columns and diagonals, we use bit masks (integers).
Each bit represents whether a column or diagonal is already occupied.

Why this works well:

Integers allow O(1) checks using bitwise operations
Uses very little memory
Faster than arrays/sets in practice

For a queen placed at position (row, col):

Column mask → bit col
Positive diagonal (/) → bit (row + col)
Negative diagonal (\) → bit (row - col + n)

If any of these bits are already set, placing a queen there causes a conflict.

We still place queens row by row, but conflict checks are done using bitwise AND.

Algorithm

Initialize three integers (bit masks):
- col → tracks used columns
- posDiag → tracks row + col
- negDiag → tracks row - col + n
Initialize an empty n x n board filled with ".".
Start backtracking from row 0.
For each c (column) in the current r (row):
- Check conflicts using bitwise AND:
  - col & (1 << c)
  - posDiag & (1 << (r + c))
  - negDiag & (1 << (r - c + n))
- If any is set → skip
If safe:
- Set bits using XOR (^=) to mark column and diagonals
- Place "Q" at (r, c)
- Recurse to row r + 1
If r == n:
- Convert the board to string format and save it
Backtrack:
- Remove the queen
- Toggle the same bits back using XOR
Continue until all valid boards are generated.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = 0
        posDiag = 0
        negDiag = 0
        res = []
        board = [["."] * n for i in range(n)]

        def backtrack(r):
            nonlocal col, posDiag, negDiag
            if r == n:
                copy = ["".join(row) for row in board]
                res.append(copy)
                return
            for c in range(n):
                if ((col & (1 << c)) or (posDiag & (1 << (r + c)))
                    or (negDiag & (1 << (r - c + n)))):
                    continue
                col ^= (1 << c)
                posDiag ^= (1 << (r + c))
                negDiag ^= (1 << (r - c + n))
                board[r][c] = "Q"

                backtrack(r + 1)

                col ^= (1 << c)
                posDiag ^= (1 << (r + c))
                negDiag ^= (1 << (r - c + n))
                board[r][c] = "."

        backtrack(0)
        return res

Time & Space Complexity

Time complexity: $O(n!)$
Space complexity: $O(n ^ 2)$

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.

Incorrect Diagonal Index Calculation

When using arrays to track diagonal occupancy, the negative diagonal row - col can produce negative indices. You must offset this value by adding n (i.e., use row - col + n) to ensure valid array indices. Forgetting this offset causes array index out of bounds errors or incorrect diagonal tracking.

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, causing the algorithm to miss valid solutions.

Scanning Below Current Row in Safety Check

Since queens are placed row by row from top to bottom, only rows above the current row can contain previously placed queens. A common error is scanning the entire column or both diagonal directions (up and down). This is wasteful at best and can cause incorrect behavior if the board is not properly initialized. Only check upward directions: the column above, upper-left diagonal, and upper-right diagonal.

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. Always convert each row to a new string and create a fresh list for each solution.