N Queens Problem in DSA Python - Build from Scratch

N Queens Problem

📖 Scenario: You are helping a chess player place n queens on an n x n chessboard. The queens must be placed so that no two queens can attack each other. This means no two queens share the same row, column, or diagonal.This classic problem is called the N Queens Problem. Your task is to find one valid arrangement of queens on the board.

🎯 Goal: Build a program that finds one valid way to place n queens on an n x n chessboard so that no two queens attack each other. The program will print the board showing queen positions.

📋 What You'll Learn

Create a variable n for the board size

Create a list board representing the chessboard rows with '.' for empty cells

Write a function is_safe(row, col) to check if placing a queen is safe

Write a recursive function solve(row) to place queens row by row

Print the final board with queens represented by 'Q'

💡 Why This Matters

🌍 Real World

The N Queens problem helps understand backtracking algorithms used in puzzles, scheduling, and constraint satisfaction problems.

💼 Career

Backtracking and recursion are common in software engineering roles involving algorithm design, game development, and AI problem solving.

1

Create the chessboard

Create a variable n and set it to 4. Then create a list called board with n strings, each string containing n dots '.' representing empty cells.

DSA Python

# Create variable n and list board with '.' for empty cells
# Your code here

Hint

Use a list comprehension to create board with n strings of dots.

2

Write the safety check function

Write a function called is_safe(row, col) that returns True if placing a queen at board[row][col] is safe. Check the same column, upper left diagonal, and upper right diagonal for existing queens 'Q'.

DSA Python

n = 4
board = ['.' * n for _ in range(n)]

# Define is_safe(row, col) function
# Your code here

Hint

Check vertically up, and diagonally up-left and up-right for queens.

3

Write the recursive solver function

Write a recursive function called solve(row) that tries to place a queen in each column of the given row. If is_safe(row, col) is True, place a queen 'Q' at board[row][col] and call solve(row + 1). If all queens are placed (row == n), return True. If no column works, backtrack by removing the queen and return False.

DSA Python

n = 4
board = ['.' * n for _ in range(n)]

def is_safe(row, col):
    for i in range(row):
        if board[i][col] == 'Q':
            return False
    i, j = row - 1, col - 1
    while i >= 0 and j >= 0:
        if board[i][j] == 'Q':
            return False
        i -= 1
        j -= 1
    i, j = row - 1, col + 1
    while i >= 0 and j < n:
        if board[i][j] == 'Q':
            return False
        i -= 1
        j += 1
    return True

# Define solve(row) recursive function
# Your code here

Hint

Try each column in the current row. Place queen if safe, then move to next row. Backtrack if needed.

4

Print the final board

Call solve(0) to start placing queens from the first row. Then print each row of the board list on a new line to show the final queen arrangement.

DSA Python

n = 4
board = ['.' * n for _ in range(n)]

def is_safe(row, col):
    for i in range(row):
        if board[i][col] == 'Q':
            return False
    i, j = row - 1, col - 1
    while i >= 0 and j >= 0:
        if board[i][j] == 'Q':
            return False
        i -= 1
        j -= 1
    i, j = row - 1, col + 1
    while i >= 0 and j < n:
        if board[i][j] == 'Q':
            return False
        i -= 1
        j += 1
    return True

def solve(row):
    if row == n:
        return True
    for col in range(n):
        if is_safe(row, col):
            board[row] = board[row][:col] + 'Q' + board[row][col+1:]
            if solve(row + 1):
                return True
            board[row] = board[row][:col] + '.' + board[row][col+1:]
    return False

# Call solve(0) and print the board rows
# Your code here

Hint

Call solve(0) to start. Then print each row of board to see the queen positions.

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