Framework Thinking - Neetcode 150 - N-Queens

Here is solutions for N-Queens.

1. Understand the problem

You are given an integer n representing an n × n chessboard.
Your task is to place n queens on the board such that:
- No two queens attack each other.
- Queens cannot share:
  - The same row
  - The same column
  - The same diagonal
Return all distinct solutions, where each solution is represented as a board of “Q” and “.”.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

What is the range of n?

Typically 1 ≤ n ≤ 9 (LeetCode), sometimes up to 14 in optimized versions.

Do we return just the count or the full board layouts?

We return all board configurations.

Are rotated/reflected boards considered different?

Yes. Only exact board layouts matter.

What is the output format?

List of boards, each board is a list of strings.

Edge cases:

n = 1 → valid ([“Q”])
n = 2 → no solution
n = 3 → no solution

3. Explore examples.

Example 1: n = 1

[["Q"]]

Example 2: n = 4

. Q . .        . . Q .
. . . Q        Q . . .
Q . . .        . . . Q
. . Q .        . Q . .

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Naive Solution - Time O((N^2)^N), Space O((N^2)^N)

Idea:
- Try all possible placements of queens in every cell.
- Check if each arrangement is valid.
Time: O((N^2)^N)
Space: O((N^2)^N)

4.2. Same idea - But you can not put Queen in the same row - Backtracking in each row - Time O(N!), Space O(N^2)

Key Idea:

Place 1 queen per row.
At each row, try every column.
Only continue if placement is safe.
Use sets to track:
- Used columns
- Used diagonals (r - c)
- Used anti-diagonals (r + c)
Time O(N!)
Space O(N!)

4.3. Solution 3 — Bitmask Optimization (Advanced, Faster) - Time O(N!), Space O(N^2)

Key Idea:

Replace sets with bitmasks (integers).
Track columns & diagonals using bit operations.
Used for large n (e.g., n = 14).

=> Same idea, but instead of store a O(N) array store only 1 interger (array bit 001010…0)

5. Implement solutions.

Question: Why time complexity is O(N!) ?

We place queens row by row.

Row 0 → up to N choices

Row 1 → at most N − 1 choices

Row 2 → at most N − 2 choices

…

Row N − 1 → at most 1 choice

=> We enforce 1 queen in 1 row, do not O(N^N).

5.1. Backtracking - Time O(N!), Space O(N^2)

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

        # Check column
        while row >= 0:
            if board[row][c] == "Q":
                return False
            row -= 1

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

        # Check right diagonal
        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: O(N!).
Space: O(N^2), space O(N^2) because check valid cost O(N^2).

5.2. Optimize DFS - Store left and right diagional - Time O(N!), Space O(N^2)

On a chessboard:

All cells on the same main diagonal have the same (row - col)
All cells on the same anti-diagonal have the same (row + col)

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: O(N!).
Space: O(N^2), O(N^2) = O(N)(sets)+O(N^2)(board)+O(N)(recursion)

5.3. Backtracking (Visited Array) - Time O(N!), Space O(N^2)

Idea:

- Same idea, but use the index of posDiag.

- Left diagional: 0, Right diagtional: n - 1, some example like this.

Idea to store posDiag[r + c] and negDiag[r - c + n] => Use an index of array to store value.

r ∈ [0, n - 1]
c ∈ [0, n - 1]

r + c ∈ [0, 2n - 2]

r - c ∈ [-(n-1), (n-1)] => Plus n to store positive index in array => r - c + n ∈ [1, 2n - 1]

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: O(N!).
Space: O(N^2), O(N^2) = O(N)(sets)+O(N^2)(board)+O(N)(recursion)

5.4. Backtracking (Bit Mask) - Same idea of (Visited Array) but store it by integer - Time O(N!), Space O(N^2)

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: O(N!).
Space: O(N^2), O(N^2) = O(1)(integer)+O(N^2)(board)+O(N)(integer)

6. Dry run testcases.

🧪 Dry Run for n = 4 (First Few Steps)

Start, place at (0, 0):

Q . . .
. . . .
. . . .
. . . .

Move to row = 1

col 0 ❌ (same column)
col 1 ❌ (diag1 = 1-1=0 conflict)
col 2 ✅

Q . . .
. . Q .
. . . .
. . . .

row = 2

col 0 ❌ column conflict
col 1 ❌ diag2 conflict
col 2 ❌ column conflict
col 3 ❌ diag1 conflict

❌ No valid → Backtrack

=> Try (1, 3)

Q . . .
. . . Q
. . . .
. . . .

Continue…

December 6, 2025