N Queens Problem in DSA Python

Mental Model

Place N queens on an NxN chessboard so that no two queens attack each other. We try positions row by row, backtracking when conflicts arise.

Analogy: Imagine seating N guests at N tables in a row, where no two guests can see each other directly across or diagonally. You try seating one guest per table, and if a conflict happens, you move the previous guest to a different seat.

Board (4x4) empty:
. . . .
. . . .
. . . .
. . . .

. = empty cell
Q = queen placed
We place queens row by row from top to bottom.

Dry Run Walkthrough

Input: N=4

Goal: Find all ways to place 4 queens on a 4x4 board so no two queens attack each other

Step 1: Place queen at row 0, column 1

Row 0: . Q . .
Row 1: . . . .
Row 2: . . . .
Row 3: . . . .

Why: Start placing the first queen in the first row at column 1

Step 2: Place queen at row 1, column 3

Row 0: . Q . .
Row 1: . . . Q
Row 2: . . . .
Row 3: . . . .

Why: Place second queen in second row at column 3 where it doesn't attack the first queen

Step 3: Try placing queen at row 2, column 0 - conflict detected

Row 0: . Q . .
Row 1: . . . Q
Row 2: Q . . . (conflict)
Row 3: . . . .

Why: Column 0 conflicts diagonally with queen at row 1, column 3

Step 4: Try placing queen at row 2, column 2 - conflict detected

Row 0: . Q . .
Row 1: . . . Q
Row 2: . . Q . (conflict)
Row 3: . . . .

Why: Column 2 conflicts diagonally with queen at row 0, column 1

Step 5: Backtrack from row 1, column 3 because no safe place in row 2

Backtrack to row 1 to try new position

Why: No safe position in row 2, so remove queen from row 1 and try next column

Step 6: Place queen at row 1, column 2

Row 0: . Q . .
Row 1: . . Q .
Row 2: . . . .
Row 3: . . . .

Why: Try next column in row 1 after backtracking

Step 7: Place queen at row 2, column 0

Row 0: . Q . .
Row 1: . . Q .
Row 2: Q . . .
Row 3: . . . .

Why: Place queen in row 2 at column 0 safely

Step 8: Place queen at row 3, column 3

Row 0: . Q . .
Row 1: . . Q .
Row 2: Q . . .
Row 3: . . . Q

Why: Place last queen safely, solution found

Result:

Solution board:
. Q . .
. . Q .
Q . . .
. . . Q

Annotated Code

DSA Python

class NQueens:
    def __init__(self, n):
        self.n = n
        self.board = [['.' for _ in range(n)] for _ in range(n)]
        self.solutions = []

    def is_safe(self, row, col):
        # Check column for another queen
        for i in range(row):
            if self.board[i][col] == 'Q':
                return False
        # Check upper left diagonal
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if self.board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        # Check upper right diagonal
        i, j = row - 1, col + 1
        while i >= 0 and j < self.n:
            if self.board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        return True

    def solve(self, row=0):
        if row == self.n:
            # Found a solution, save a copy
            solution = [''.join(r) for r in self.board]
            self.solutions.append(solution)
            return
        for col in range(self.n):
            if self.is_safe(row, col):
                self.board[row][col] = 'Q'  # Place queen
                self.solve(row + 1)         # Move to next row
                self.board[row][col] = '.'  # Remove queen (backtrack)

if __name__ == '__main__':
    n = 4
    solver = NQueens(n)
    solver.solve()
    for sol in solver.solutions:
        for row in sol:
            print(row)
        print()

for i in range(row): if self.board[i][col] == 'Q': return False

check column above current row for queen conflict

i, j = row - 1, col - 1 while i >= 0 and j >= 0: if self.board[i][j] == 'Q': return False i -= 1 j -= 1

check upper left diagonal for queen conflict

i, j = row - 1, col + 1 while i >= 0 and j < self.n: if self.board[i][j] == 'Q': return False i -= 1 j += 1

check upper right diagonal for queen conflict

if row == self.n: solution = [''.join(r) for r in self.board] self.solutions.append(solution) return

all rows processed, save current board as a solution

if self.is_safe(row, col): self.board[row][col] = 'Q' self.solve(row + 1) self.board[row][col] = '.'

place queen, recurse to next row, then backtrack by removing queen

Output

..Q.

Q...

...Q

.Q..



.Q..

...Q

Q...

..Q.

Complexity Analysis

Time: O(N!) because each row tries N columns and backtracks, pruning invalid positions

Space: O(N^2) for the board storage and O(N) recursion stack for rows

vs Alternative: Naive brute force tries all N^N placements, which is much slower than backtracking pruning invalid states early

Edge Cases

N=1 (smallest board)

One queen placed on the single cell, solution found immediately

DSA Python

if row == self.n:

N=2 or N=3 (no solutions)

Backtracking tries all positions but finds no valid solutions, returns empty list

DSA Python

if row == self.n:

Large N (e.g., N=8)

Algorithm finds all solutions but takes longer due to combinatorial complexity

DSA Python

if self.is_safe(row, col):

When to Use This Pattern

When you see a problem asking to place items on a grid with constraints and no conflicts, reach for backtracking because it tries options step-by-step and undoes choices when stuck.

Common Mistakes

Mistake: Not checking all three directions (column and both diagonals) for queen conflicts
Fix: Add checks for column, upper left diagonal, and upper right diagonal before placing a queen

Mistake: Not backtracking (removing queen) after recursive call
Fix: After recursive call, reset the cell to empty to explore other possibilities

Summary

Find all ways to place N queens on an NxN board so no two queens attack each other.

Use backtracking when you need to explore all valid configurations with constraints.

Try placing queens row by row, checking safety, and backtrack when stuck.

Practice

1. What is the main goal of the N Queens Problem?

easy

A. Place N queens on an NxN chessboard so that no two queens attack each other

B. Count the total number of queens on a chessboard

C. Move queens to capture all opponent pieces

D. Arrange queens in a single row on the chessboard

Solution

1. Step 1: Understand the problem statement

   The N Queens Problem requires placing N queens on an NxN board so that no two queens threaten each other.

2. Step 2: Analyze the options

   Only Place N queens on an NxN chessboard so that no two queens attack each other correctly describes placing queens so none attack each other. Other options describe unrelated tasks.

3. Final Answer:

   Place N queens on an NxN chessboard so that no two queens attack each other -> Option A

4. Quick Check:

   Goal = Place queens safely [OK]

Hint: Remember: no two queens can share row, column, or diagonal [OK]

Common Mistakes:

• Thinking queens can be in the same row or column
• Confusing the problem with counting queens
• Assuming queens can attack each other

2. Which of the following Python code snippets correctly initializes an empty chessboard for the N Queens Problem with size n?

easy

A. board = [[0 for _ in range(n)] for _ in range(n)]

B. board = [[0]*n]

C. board = [0]*n

D. board = [[0]*n]*n

Solution

1. Step 1: Understand board initialization

   We need a 2D list with independent rows to represent the chessboard.

2. Step 2: Analyze each option

   board = [[0]*n]*n creates rows referencing the same list, causing bugs. board = [[0 for _ in range(n)] for _ in range(n)] creates independent rows correctly. board = [0]*n creates a 1D list, not 2D. board = [[0]*n] creates a single row only.

3. Final Answer:

   board = [[0 for _ in range(n)] for _ in range(n)] -> Option A

4. Quick Check:

   Independent rows = board = [[0 for _ in range(n)] for _ in range(n)] [OK]

Hint: Use nested list comprehension for independent rows [OK]

Common Mistakes:

• Using [[0]*n]*n causing shared references
• Creating 1D list instead of 2D
• Forgetting to repeat for each row

3. What will be the output of the following Python code snippet for n = 4?

def is_safe(board, row, col):
    for i in range(col):
        if board[row][i] == 1:
            return False
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    for i, j in zip(range(row, len(board), 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    return True

board = [[0]*4 for _ in range(4)]
board[1][0] = 1
print(is_safe(board, 1, 1))
print(is_safe(board, 0, 1))

medium

A. True\nFalse

B. False\nFalse

C. False\nTrue

D. True\nTrue

Solution

1. Step 1: Check is_safe for position (1,1)

   Column check: board[1][0] == 1, so returns False.

2. Step 2: Check is_safe for position (0,1)

   Row left: board[0][0] == 0. Upper diagonal: board[0][1] == 0. Lower diagonal: board[1][0] == 1, so returns False.

3. Final Answer:

   False\nFalse -> Option B

4. Quick Check:

   Check columns and diagonals = False, False [OK]

Hint: Check columns and diagonals left of position [OK]

Common Mistakes:

• Ignoring diagonal checks
• Confusing row and column indices
• Assuming safe if no queen in same row only

4. Identify the error in the following code snippet for solving the N Queens Problem:

def solve_n_queens(board, col):
    if col >= len(board):
        return True
    for row in range(len(board)):
        if is_safe(board, row, col):
            board[row][col] = 1
            if solve_n_queens(board, col + 1):
                return True
            board[row][col] = 0
    return False

board = [[0]*4 for _ in range(4)]
solve_n_queens(board, 0)
print(board)

medium

A. The base case condition is incorrect

B. The board is not reset properly after backtracking

C. The function returns True too early, missing all solutions

D. The is_safe function is not called

Solution

1. Step 1: Analyze the recursion and return statements

   The function returns True immediately after finding the first solution, so it stops searching further.

2. Step 2: Understand impact on solution finding

   This means it finds only one solution and does not explore all possible solutions.

3. Final Answer:

   The function returns True too early, missing all solutions -> Option C

4. Quick Check:

   Early return stops full search [OK]

Hint: Return True only after exploring all columns [OK]

Common Mistakes:

• Stopping recursion after first solution
• Not resetting board on backtrack
• Incorrect base case check

5. Given the N Queens Problem, which approach best improves efficiency by reducing unnecessary checks during queen placement?

hard

A. Place queens randomly and retry if conflicts occur

B. Check the entire board for conflicts every time before placing a queen

C. Use nested loops to try all possible board configurations without pruning

D. Use backtracking with arrays to track columns and diagonals already occupied

Solution

1. Step 1: Understand efficiency in N Queens

   Checking the entire board repeatedly wastes time; pruning reduces checks.

2. Step 2: Analyze options for pruning

   Using arrays to track columns and diagonals occupied avoids repeated scanning, improving speed.

3. Final Answer:

   Use backtracking with arrays to track columns and diagonals already occupied -> Option D

4. Quick Check:

   Pruning with tracking arrays = Use backtracking with arrays to track columns and diagonals already occupied [OK]

Hint: Track columns and diagonals to skip invalid spots fast [OK]

Common Mistakes:

• Checking full board every time
• Trying random placements without pruning
• Using brute force without backtracking