Day 49: N-Queens Problem#

Welcome to Day 49 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive deep into the N-Queens Problem, a classic example of backtracking algorithms.

What is the N-Queens Problem?#

The N-Queens Problem is the challenge of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

Understanding the Problem#

• We have an N×N chessboard.
• We need to place N queens on this board.
• No two queens should be able to attack each other.
• A queen can attack any piece in its row, column, or diagonals.

Backtracking Approach#

We’ll use a backtracking approach to solve this problem:

1. Start in the leftmost column.
2. If all queens are placed, return true.
3. Try all rows in the current column:
   • If the queen can be placed safely, mark this as part of the solution.
   • Recursively check if placing the queen here leads to a solution.
   • If placing the queen leads to a solution, return true.
   • If placing the queen doesn’t lead to a solution, unmark this and try the next row.
4. If all rows have been tried and nothing worked, return false.

Implementation#

Here’s a Python implementation of the N-Queens Problem:

 1def solve_n_queens(n):
 2    def is_safe(board, row, col):
 3        # Check this row on left side
 4        for i in range(col):
 5            if board[row][i] == 1:
 6                return False
 7        
 8        # Check upper diagonal on left side
 9        for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
10            if board[i][j] == 1:
11                return False
12        
13        # Check lower diagonal on left side
14        for i, j in zip(range(row, n, 1), range(col, -1, -1)):
15            if board[i][j] == 1:
16                return False
17        
18        return True
19
20    def solve(board, col):
21        if col >= n:
22            return True
23        
24        for i in range(n):
25            if is_safe(board, i, col):
26                board[i][col] = 1
27                if solve(board, col + 1):
28                    return True
29                board[i][col] = 0
30        
31        return False
32
33    def print_solution(board):
34        for row in board:
35            print(" ".join("Q" if x else "." for x in row))
36
37    board = [[0 for _ in range(n)] for _ in range(n)]
38    
39    if solve(board, 0):
40        print_solution(board)
41    else:
42        print("Solution does not exist")
43
44# Example usage
45solve_n_queens(8)

Time Complexity#

The time complexity of the N-Queens problem is O(N!), as in the worst case, we are exploring all possible configurations.

Space Complexity#

The space complexity is O(N^2) to store the chessboard.

Optimizations#

1. Bitwise Operations: We can use bitwise operations to check for conflicts, which can significantly speed up the algorithm.
2. Symmetry: We can reduce the search space by considering symmetries of the board.
3. Iterative Deepening: We can use iterative deepening to find solutions for smaller boards first.

Variations of the Problem#

1. Count all possible solutions: Instead of finding one solution, count all possible solutions.
2. N-Queens Completion Problem: Given some queens already on the board, complete the solution.
3. N-Rooks Problem: Place N rooks on an N×N chessboard so that no two rooks threaten each other.

Real-world Applications#

While the N-Queens problem itself is primarily academic, the techniques used to solve it have applications in:

1. Constraint satisfaction problems
2. VLSI chip design
3. Parallel memory storage schemes
4. Traffic control systems

Exercise#

1. Modify the solution to print all possible solutions for a given N.
2. Implement an iterative (non-recursive) solution to the N-Queens problem.
3. Solve the N-Queens Completion Problem: Given a partially filled board, complete it if possible.

Summary#

Today, we explored the N-Queens Problem, a classic example of backtracking algorithms. We implemented a solution, discussed its time and space complexity, and looked at possible optimizations and variations of the problem.

The N-Queens problem demonstrates the power of backtracking in solving complex combinatorial problems. The techniques we’ve learned here can be applied to a wide range of problems in computer science and beyond.

Tomorrow, we’ll dive into another classic backtracking problem: Sudoku Solver. Stay tuned!

Solution#

 1# Exercise 1: Count and collect ALL solutions for a given N.
 2# We place one queen per row and track occupied columns and diagonals with sets.
 3def solve_all_n_queens(n):
 4    solutions = []
 5    cols = set()          # Occupied columns.
 6    diag = set()          # Occupied "/" diagonals (row + col).
 7    anti_diag = set()     # Occupied "\" diagonals (row - col).
 8    placement = [-1] * n  # placement[row] = column of the queen in that row.
 9
10    def backtrack(row):
11        if row == n:
12            solutions.append(placement[:])
13            return
14        for col in range(n):
15            if col in cols or (row + col) in diag or (row - col) in anti_diag:
16                continue  # This column or diagonal is attacked.
17            cols.add(col); diag.add(row + col); anti_diag.add(row - col)
18            placement[row] = col
19            backtrack(row + 1)
20            cols.remove(col); diag.remove(row + col); anti_diag.remove(row - col)
21
22    backtrack(0)
23    return solutions
24
25boards = solve_all_n_queens(4)
26print("Number of solutions:", len(boards))  # 2
27for cols in boards:
28    for c in cols:
29        print("".join("Q" if i == c else "." for i in range(4)))
30    print()