Day 49: N-Queens Problem

Table of Contents

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:

def solve_n_queens(n):
    def is_safe(board, row, col):
        # Check this row on left side
        for i in range(col):
            if board[row][i] == 1:
                return False
        
        # Check upper diagonal on left side
        for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
            if board[i][j] == 1:
                return False
        
        # Check lower diagonal on left side
        for i, j in zip(range(row, n, 1), range(col, -1, -1)):
            if board[i][j] == 1:
                return False
        
        return True

    def solve(board, col):
        if col >= n:
            return True
        
        for i in range(n):
            if is_safe(board, i, col):
                board[i][col] = 1
                if solve(board, col + 1):
                    return True
                board[i][col] = 0
        
        return False

    def print_solution(board):
        for row in board:
            print(" ".join("Q" if x else "." for x in row))

    board = [[0 for _ in range(n)] for _ in range(n)]
    
    if solve(board, 0):
        print_solution(board)
    else:
        print("Solution does not exist")

# Example usage
solve_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!