Python Program to Solve N Queens Problem

You can solve the N Queens problem in Python using backtracking by placing queens row by row and checking if each placement is safe with a function like is_safe(), then recursively trying to place queens in the next row until all are placed.

Examples

Inputn = 1

Output[["Q"]]

Inputn = 4

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

Inputn = 2

Output[]

How to Think About It

To solve the N Queens problem, think of placing one queen in each row. For each row, try placing a queen in each column and check if it is safe (no other queen attacks it). If safe, move to the next row. If no safe spot is found, backtrack to the previous row and try a different column. Repeat until all queens are placed or no solution exists.

Algorithm

1

Start with the first row.

2

Try placing a queen in each column of the current row.

3

Check if placing the queen is safe (no attacks from other queens).

4

If safe, move to the next row and repeat.

5

If no column is safe, backtrack to the previous row and try a different column.

6

When all rows have queens placed safely, record the solution.

Code

python

def solve_n_queens(n):
    def is_safe(row, col):
        for r in range(row):
            c = positions[r]
            if c == col or abs(c - col) == abs(r - row):
                return False
        return True

    def backtrack(row):
        if row == n:
            board = []
            for r in range(n):
                line = ['.'] * n
                line[positions[r]] = 'Q'
                board.append(''.join(line))
            solutions.append(board)
            return
        for col in range(n):
            if is_safe(row, col):
                positions[row] = col
                backtrack(row + 1)

    solutions = []
    positions = [-1] * n
    backtrack(0)
    return solutions

# Example usage
n = 4
result = solve_n_queens(n)
print(result)

Output

[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]

Dry Run

Let's trace n=4 through the code

1

Start with row 0

Try columns 0 to 3; place queen at column 1 (safe). positions = [1, -1, -1, -1]

2

Move to row 1

Try columns 0 to 3; column 3 is safe. positions = [1, 3, -1, -1]

3

Move to row 2

Try columns 0 to 3; column 0 is safe. positions = [1, 3, 0, -1]

4

Move to row 3

Try columns 0 to 3; column 2 is safe. positions = [1, 3, 0, 2]

5

All queens placed

Record solution: ['.Q..', '...Q', 'Q...', '..Q.']

6

Backtrack to find other solutions

Try other columns in previous rows to find second solution.

Row	Positions Array
0	[1, -1, -1, -1]
1	[1, 3, -1, -1]
2	[1, 3, 0, -1]
3	[1, 3, 0, 2]

Why This Works

Step 1: Check safety of queen placement

The is_safe function ensures no other queen is in the same column or diagonal by comparing positions of previously placed queens.

Step 2: Use backtracking to explore options

The backtrack function tries placing queens row by row, and if stuck, it goes back to try different columns, exploring all possibilities.

Step 3: Store valid solutions

When all queens are placed safely, the current board configuration is converted to strings and saved in solutions.

Alternative Approaches

Bitmasking approach

python

def solve_n_queens_bitmask(n):
    def backtrack(row=0, cols=0, diags1=0, diags2=0):
        if row == n:
            return 1
        count = 0
        available_positions = ((1 << n) - 1) & ~(cols | diags1 | diags2)
        while available_positions:
            position = available_positions & -available_positions
            available_positions &= available_positions - 1
            count += backtrack(row + 1, cols | position, (diags1 | position) << 1, (diags2 | position) >> 1)
        return count
    return backtrack()

print(solve_n_queens_bitmask(4))

This method is faster and uses bit operations to track attacks but is harder to understand for beginners.

Iterative approach with stack

python

def solve_n_queens_iterative(n):
    stack = [(-1, [])]
    solutions = []
    while stack:
        row, positions = stack.pop()
        row += 1
        if row == n:
            solutions.append(positions)
            continue
        for col in range(n):
            if all(col != c and abs(col - c) != row - r for r, c in enumerate(positions)):
                stack.append((row, positions + [col]))
    return solutions

print(solve_n_queens_iterative(4))

This uses a stack to simulate recursion but is more complex and less intuitive.

Complexity: O(n!) time, O(n) space

Time Complexity

The algorithm tries to place queens in each row and column, pruning invalid positions early. The worst case explores factorial possibilities, so time is O(n!).

Space Complexity

We store positions for each queen in an array of size n and recursion stack depth is n, so space is O(n).

Which Approach is Fastest?

Bitmasking is fastest due to efficient bit operations, but backtracking with arrays is easier to understand and implement.

Approach	Time	Space	Best For
Backtracking with arrays	O(n!)	O(n)	Easy to understand and implement
Bitmasking	O(n!) but faster in practice	O(n)	Performance-critical solutions
Iterative with stack	O(n!)	O(n)	Avoid recursion, but more complex