52. N Queens II - Explanation

Problem Link

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.

You are given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4

Output: 2

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

Example 2:

Input: n = 1

Output: 1

Constraints:

  • 1 <= n <= 9


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Backtracking

Intuition

We place queens row by row, ensuring each placement is valid before moving to the next row. For each column in the current row, we check if placing a queen there would conflict with any queen already placed above. A queen attacks along its column and both diagonals, so we scan upward in those three directions. If no conflict exists, we place the queen and recurse to the next row. When we successfully place queens in all rows, we have found a valid configuration.

Algorithm

  1. Initialize a res counter for valid solutions and create an empty board.
  2. Define a backtracking function that takes the current r (row):
    • If r equals n, increment the solution count and return.
    • For each c (column) in the row:
      • Check if the position is isSafe by scanning the column above, the upper-left diagonal, and the upper-right diagonal for existing queens.
      • If safe, place a queen at this position.
      • Recursively call backtrack for the next row.
      • Remove the queen (backtrack) to try other columns.
  3. Start backtracking from row 0 and return the final count.
class Solution:
    def totalNQueens(self, n: int) -> int:
        res = 0
        board = [["."] * n for i in range(n)]

        def backtrack(r):
            nonlocal res
            if r == n:
                res += 1
                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!)O(n!)
  • Space complexity: O(n2)O(n ^ 2)

2. Backtracking (Hash Set)

Intuition

Instead of scanning the board to check for conflicts, we can track which columns and diagonals are already occupied using hash sets. Each column has a unique index. For diagonals, cells on the same positive diagonal (bottom-left to top-right) share the same value of row + col, while cells on the same negative diagonal (top-left to bottom-right) share the same value of row - col. By checking set membership, we determine in constant time whether a position is under attack.

Algorithm

  1. Create three hash sets: one for col (columns), one for posDiag (positive diagonals with row + col), and one for negDiag (negative diagonals with row - col).
  2. Define a backtracking function that takes the current r (row):
    • If r equals n, increment the solution count and return.
    • For each c (column) in the row:
      • If c or either diagonal is already in the corresponding set, skip this column.
      • Add c and both diagonal identifiers to their respective sets.
      • Recursively call backtrack for the next row.
      • Remove c and diagonal identifiers from the sets (backtrack).
  3. Start backtracking from row 0 and return the final count.
class Solution:
    def totalNQueens(self, n: int) -> int:
        col = set()
        posDiag = set()
        negDiag = set()

        res = 0
        def backtrack(r):
            nonlocal res
            if r == n:
                res += 1
                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)

                backtrack(r + 1)

                col.remove(c)
                posDiag.remove(r + c)
                negDiag.remove(r - c)

        backtrack(0)
        return res

Time & Space Complexity

  • Time complexity: O(n!)O(n!)
  • Space complexity: O(n)O(n)

3. Backtracking (Boolean Array)

Intuition

Hash sets have some overhead for insertions and lookups. Since the board size is fixed and the range of diagonal indices is bounded, we can use boolean arrays instead. An array of size n tracks occupied columns, and arrays of size 2n track the positive and negative diagonals. For negative diagonals, we add n to the index to ensure non-negative array indices. This gives us the same constant-time conflict checking with lower overhead.

Algorithm

  1. Create three boolean arrays: col[n], posDiag[2n], and negDiag[2n].
  2. Define a backtracking function that takes the current r (row):
    • If r equals n, increment the solution count and return.
    • For each c (column) in the row:
      • Check col[c], posDiag[r + c], and negDiag[r - c + n]. If any is true, skip this column.
      • Set all three to true.
      • Recursively call backtrack for the next row.
      • Set all three back to false (backtrack).
  3. Start backtracking from row 0 and return the final count.
class Solution:
    def totalNQueens(self, n: int) -> int:
        col = [False] * n
        posDiag = [False] * (n * 2)
        negDiag = [False] * (n * 2)
        res = 0

        def backtrack(r):
            nonlocal res
            if r == n:
                res += 1
                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

                backtrack(r + 1)

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

        backtrack(0)
        return res

Time & Space Complexity

  • Time complexity: O(n!)O(n!)
  • Space complexity: O(n)O(n)

4. Backtracking (Bit Mask)

Intuition

Bit manipulation offers the most compact representation for tracking occupied columns and diagonals. We use three integers as bitmasks: each bit in col represents whether that column is occupied, and similarly for the two diagonal masks. Checking if a position is attacked becomes a single bitwise AND operation. Setting and unsetting bits is done with XOR. This approach is both space-efficient and cache-friendly.

Algorithm

  1. Initialize three integers col, posDiag, and negDiag to 0.
  2. Define a backtracking function that takes the current r (row):
    • If r equals n, increment the solution count and return.
    • For each c (column) in the row:
      • Check if the bit at position c in col, position r + c in posDiag, or position r - c + n in negDiag is set. If any is set, skip this column.
      • Toggle the corresponding bits using XOR.
      • Recursively call backtrack for the next row.
      • Toggle the bits again to restore the previous state (backtrack).
  3. Start backtracking from row 0 and return the final count.
class Solution:
    def totalNQueens(self, n: int) -> int:
        col = 0
        posDiag = 0
        negDiag = 0
        res = 0

        def backtrack(r):
            nonlocal col, posDiag, negDiag, res
            if r == n:
                res += 1
                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))

                backtrack(r + 1)

                col ^= (1 << c)
                posDiag ^= (1 << (r + c))
                negDiag ^= (1 << (r - c + n))

        backtrack(0)
        return res

Time & Space Complexity

  • Time complexity: O(n!)O(n!)
  • Space complexity: O(n)O(n) for 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 incorrect solution counts.

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). Failing to properly backtrack leaves stale state that incorrectly blocks future valid placements, causing the algorithm to miss solutions or count incorrectly.

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.