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!