Backtracking Algorithms: N-Queens, Job Scheduling, Knapsack, and Bellman-Ford

Posted on Dec 17, 2024 in Computers

N-Queens Problem and Backtracking

The N-Queens problem is a classic computer science challenge. The goal is to place N queens on an N×N chessboard so that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal.

Constraints:

  • N queens must be placed on the board.
  • No two queens should be on the same row, column, or diagonal.

Backtracking Algorithm

Backtracking explores all possible queen placements using a depth-first search. It builds the solution step by step and backtracks upon detecting a conflict.


def is_safe(row, col):
    # Check column and diagonals for conflict
    for i in range(row):
        if board[i] == col or abs(board[i] - col) == row - i:
            return False
    return True

def place_queen(row):
    if row == N:  # All queens are placed
        solutions.append(board[:])
        return
    for col in range(N):
        if is_safe(row, col):
            board[row] = col
            place_queen(row + 1)  # Place queen in the next row
            board[row] = -1  # Backtrack (remove queen)

place_queen(0)
return solutions

Time Complexity:

The time complexity is O(N!) due to the exploration of all possible placements.

Job Sequencing with Deadlines

The Job Sequencing with Deadlines problem aims to maximize profit by scheduling jobs with deadlines.

Problem Definition:

Given a set of jobs J={J1,J2,…,Jn}, each job Ji has:

  • A deadline di (the time by which the job must be completed).
  • A profit pi (the profit gained if the job is completed before its deadline).

The objective is to schedule jobs to maximize total profit, ensuring only one job is scheduled at a time and each job is completed before its deadline.

Approach:

  1. Sort Jobs by Profit: Sort jobs in descending order of profit.
  2. Scheduling Jobs: For each job, check if it can be scheduled before its deadline. If yes, schedule it; otherwise, discard it.

Time Complexity:

  • Sorting: O(n log n)
  • Job Scheduling: O(n2)

The overall time complexity is O(n2).

Space Complexity:

The space complexity is O(n).

0/1 Knapsack Problem

The 0/1 Knapsack Problem is an optimization problem where the goal is to maximize the total value of items placed in a knapsack with a weight limit.

Problem Definition:

Given a set of n items, each with a weight wi and a value vi, and a knapsack with a maximum weight capacity W, the goal is to determine the maximum total value of items that can be placed in the knapsack such that:

  • The total weight of the selected items does not exceed the capacity W.
  • Each item can either be included (1) or excluded (0).

Backtracking Approach:


def knapsack_backtracking(weights, values, W, n):
    # Helper function to recursively explore the knapsack's options
    def knapsack_recursive(index, remaining_capacity, current_value):
        # Base case: No more items or capacity
        if index == n or remaining_capacity == 0:
            return current_value
        # Case 1: Exclude the current item
        exclude = knapsack_recursive(index + 1, remaining_capacity, current_value)
        # Case 2: Include the current item (if it fits in the remaining capacity)
        include = 0
        if weights[index] <= remaining_capacity:
            include = knapsack_recursive(index + 1, remaining_capacity - weights[index], current_value + values[index])
        # Return the maximum of including or excluding the current item
        return max(exclude, include)
    return knapsack_recursive(0, W, 0)

Time Complexity:

The time complexity is O(2n) due to the exploration of all subsets of items.

Space Complexity:

The space complexity is O(n) due to the recursion stack.

Bellman-Ford Algorithm and Negative Weight Cycles

The Bellman-Ford Algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph, including those with negative weights. It can also detect negative weight cycles.

Negative Weight Cycle Detection:

The algorithm iteratively relaxes all edges in the graph. After n-1 iterations, if any edge can still be relaxed, it indicates a negative weight cycle.

Example:

Graph Representation:


Vertices: V={0,1,2,3}
Edges:
0→1 (weight = 1)
1→2 (weight = -1)
2→3 (weight = -1)
3→1 (weight = -1)

Step-by-Step Execution:

Initialization:

distance=[0,∞,∞,∞]

Relaxation (3 iterations):

  • Relax 0→1: distance[1]=0+1=1
  • Relax 1→2: distance[2]=1−1=0
  • Relax 2→3: distance[3]=0−1=−1

Iteration 1:

distance=[0,−2,0,−1]

Iteration 2 and 3: Further relaxations occur, reducing distances further.

Negative Weight Cycle Detection:

After n−1=3 iterations, perform a fourth iteration. If any distance is further reduced, it indicates a negative weight cycle.