DEV Community: b

Finds the shortest path on a 2D grid (with obstacles) using the A* search algorithm.

Fri, 28 Mar 2025 03:38:14 +0000

# Find Best Path in 2D Grid with Obstacles - A* Search Algorithm
# Description: Finds the shortest path on a 2D grid (with obstacles) using the A* search algorithm.

import heapq

def manhattan_distance(point_a, point_b):
    """
    Calculate the Manhattan distance between two points.

    Args:
        point_a (tuple): First point (row, col)
        point_b (tuple): Second point (row, col)

    Returns:
        int: Manhattan distance between the points
    """
    return abs(point_a[0] - point_b[0]) + abs(point_a[1] - point_b[1])

def is_valid_move(grid, point):
    """
    Check if a point is a valid move on the grid.

    Args:
        grid (list of list): 2D grid where 1 represents obstacles
        point (tuple): Point to check (row, col)

    Returns:
        bool: True if the point is a valid move, False otherwise
    """
    row, col = point
    return (0 <= row < len(grid) and 
            0 <= col < len(grid[0]) and 
            grid[row][col] != 1)

def reconstruct_path(came_from, current):
    """
    Reconstruct the path from start to goal.

    Args:
        came_from (dict): Dictionary tracking the previous point for each point
        current (tuple): Goal point

    Returns:
        list: Path from start to goal
    """
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    return path[::-1]

def a_star(start, goal, grid):
    """
    Find the shortest path in a 2D grid using A* search algorithm.

    Args:
        start (tuple): Starting point (row, col)
        goal (tuple): Goal point (row, col)
        grid (list of list): 2D grid where 1 represents obstacles

    Returns:
        list or str: Path from start to goal, or "No path found"

    Example:
        grid = [
            [0, 0, 0, 0],
            [0, 1, 1, 0],
            [0, 0, 0, 0],
            [0, 1, 0, 0]
        ]
        start = (0, 0)
        goal = (3, 3)
        path = a_star(start, goal, grid)
    """
    # Possible movement directions: right, down, left, up
    DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    # Priority queue to store nodes to explore
    # Format: (f_score, g_score, point)
    open_set = []
    heapq.heappush(open_set, (manhattan_distance(start, goal), 0, start))

    # Track the path and movement costs
    came_from = {}
    g_score = {start: 0}

    while open_set:
        # Get the node with the lowest f_score
        _, current_cost, current = heapq.heappop(open_set)

        # Check if we've reached the goal
        if current == goal:
            return reconstruct_path(came_from, current)

        # Explore neighboring cells
        for dx, dy in DIRECTIONS:
            neighbor = (current[0] + dx, current[1] + dy)

            # Skip invalid moves
            if not is_valid_move(grid, neighbor):
                continue

            # Calculate tentative movement cost
            tentative_cost = current_cost + 1

            # Update if this is a better path
            if neighbor not in g_score or tentative_cost < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_cost

                # Calculate f_score (total estimated cost)
                f_score = tentative_cost + manhattan_distance(neighbor, goal)
                heapq.heappush(open_set, (f_score, tentative_cost, neighbor))

    # No path found
    return "No path found"

Determines the fewest coins needed to make up a given amount using a greedy algorithm.

Fri, 28 Mar 2025 03:37:56 +0000

# Coin Change - Greedy Approach
# Description: Determines the fewest coins needed to make up a given amount using a greedy algorithm.

def coin_change(coins, amount):
    """
    Solve the coin change problem using a greedy algorithm.

    Determines the minimum number of coins needed to make up a specified amount
    by selecting the largest possible coins first.

    Args:
        coins (list of int): Available coin denominations.
        amount (int): Target monetary amount to make change for.

    Returns:
        list or str: Coins used to make the amount, or "Not possible" if no solution.

    Key Characteristics:
    - Prioritizes larger coin denominations
    - Minimizes total number of coins used
    - Works perfectly for some coin systems (e.g., US coins)
    - May fail for certain coin denomination sets

    Time Complexity: O(n log n), where n is the number of coin denominations
    Space Complexity: O(amount)

    Note: Greedy approach is not guaranteed to work for all possible coin sets.
    """
    # Validate input
    if amount < 0:
        return "Not possible"

    # Handle zero amount
    if amount == 0:
        return []

    # Sort coins in descending order to prioritize larger denominations
    sorted_coins = sorted(coins, reverse=True)

    # Coin selection process
    result = []
    remaining = amount

    # Iterate through coin denominations
    for coin in sorted_coins:
        # Use the largest possible coins first
        while remaining >= coin:
            result.append(coin)
            remaining -= coin

        # Early exit if exact amount is reached
        if remaining == 0:
            return result

    # Check if a complete solution was found
    return result if remaining == 0 else "Not possible"

def coin_change_dynamic_programming(coins, amount):
    """
    Solve the coin change problem using dynamic programming.

    A more robust approach that guarantees finding the minimum number of coins
    for any valid set of coin denominations.

    Args:
        coins (list of int): Available coin denominations.
        amount (int): Target monetary amount to make change for.

    Returns:
        list or str: Minimum number of coins used, or "Not possible" if no solution.

    Key Characteristics:
    - Guaranteed to find the optimal solution
    - Works for all coin denomination sets
    - More computationally expensive than greedy approach

    Time Complexity: O(amount * len(coins))
    Space Complexity: O(amount)
    """
    # Validate input
    if amount < 0:
        return "Not possible"

    # Handle zero amount
    if amount == 0:
        return []

    # Dynamic programming table
    # dp[i] will store the minimum number of coins for amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    # Track the coins used for each amount
    coin_used = [[] for _ in range(amount + 1)]

    # Build solution bottom-up
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                # Check if using this coin leads to a better solution
                if dp[i - coin] + 1 < dp[i]:
                    dp[i] = dp[i - coin] + 1
                    coin_used[i] = coin_used[i - coin] + [coin]

    # Return solution or "Not possible"
    return coin_used[amount] if dp[amount] != float('inf') else "Not possible"

# Demonstration function
def demonstrate_coin_change():
    """
    Demonstrate coin change solving with various scenarios.
    """
    test_cases = [
        # US coin denominations
        {
            'coins': [1, 5, 10, 25, 50],
            'amounts': [63, 99, 42]
        },
        # International coin set
        {
            'coins': [1, 2, 5, 10, 20, 50, 100],
            'amounts': [73, 45, 17]
        },
        # Challenging coin set
        {
            'coins': [11, 7, 5],
            'amounts': [15, 22, 33]
        }
    ]

    for case in test_cases:
        coins = case['coins']
        print(f"\nCoin Denominations: {coins}")

        for amount in case['amounts']:
            print(f"\nAmount: {amount}")
            print("Greedy Approach:     ", coin_change(coins, amount))
            print("Dynamic Programming:", coin_change_dynamic_programming(coins, amount))

Colors a graph so that no two adjacent vertices share the same color using a backtracking approach.

Fri, 28 Mar 2025 03:37:39 +0000

# Graph Coloring - Backtracking
# Description: Colors a graph so that no two adjacent vertices share the same color using a backtracking approach.

def graph_coloring(graph, num_colors):
    """
    Color a graph using backtracking to ensure no adjacent nodes share a color.

    This algorithm attempts to assign colors to graph nodes such that no 
    two adjacent nodes have the same color, using the minimum number of colors possible.

    Args:
        graph (dict): Adjacency list representing graph connections.
        num_colors (int): Maximum number of colors available for coloring.

    Returns:
        dict: Mapping of nodes to colors, or None if no valid coloring exists.

    Time Complexity: O(num_colors^V), where V is the number of vertices
    Space Complexity: O(V)

    Note: This is an NP-hard problem, so the algorithm uses backtracking.
    """
    # Initialize coloring with uncolored nodes
    coloring = {node: -1 for node in graph}
    nodes = list(graph.keys())

    def is_color_valid(node, color):
        """
        Check if a color can be assigned to a node without conflicts.

        Args:
            node (int): Current node being colored
            color (int): Color being considered

        Returns:
            bool: True if color can be assigned, False otherwise
        """
        # Check all adjacent nodes to ensure no color conflicts
        for neighbor in graph[node]:
            # Skip uncolored neighbors
            if coloring[neighbor] == -1:
                continue
            # Check for color conflict with colored neighbors
            if coloring[neighbor] == color:
                return False
        return True

    def backtrack_color(node_index):
        """
        Recursive backtracking function to color the graph.

        Args:
            node_index (int): Index of the current node being processed

        Returns:
            bool: True if a valid coloring is found, False otherwise
        """
        # Base case: all nodes have been colored successfully
        if node_index == len(nodes):
            return True

        # Get the current node to color
        current_node = nodes[node_index]

        # Try coloring the current node with each available color
        for color in range(num_colors):
            # Check if the current color is valid for this node
            if is_color_valid(current_node, color):
                # Assign the color
                coloring[current_node] = color

                # Recursively try to color the next node
                if backtrack_color(node_index + 1):
                    return True

                # Backtrack: reset the color if solution not found
                coloring[current_node] = -1

        # No valid coloring found
        return False

    # Attempt to color the graph
    return coloring if backtrack_color(0) else None

Finds the contiguous subarray within a one-dimensional array of numbers that has the largest sum.

Fri, 28 Mar 2025 03:37:29 +0000

# Maximum Subarray Sum - Kadane's Algorithm
# Description: Finds the contiguous subarray within a one-dimensional array of numbers that has the largest sum.

def max_subarray(nums):
    """
    Find the maximum sum of a contiguous subarray using Kadane's Algorithm.

    This algorithm efficiently solves the maximum subarray problem by 
    dynamically tracking the maximum sum ending at each position.

    Time Complexity: O(n)
    Space Complexity: O(1)

    Args:
        nums (list of int): Input array of integers

    Returns:
        int: Maximum sum of any contiguous subarray

    Raises:
        ValueError: If the input list is empty

    Example:
        >>> max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])
        6
        >>> max_subarray([1])
        1
        >>> max_subarray([-1, -2, -3])
        -1
    """
    # Handle empty input
    if not nums:
        raise ValueError("Input list cannot be empty")

    # Initialize with the first element
    max_sum = current_sum = nums[0]

    # Iterate through the array starting from the second element
    for num in nums[1:]:
        # Decide whether to start a new subarray or extend the current one
        # This is the core of Kadane's algorithm
        current_sum = max(num, current_sum + num)

        # Update the overall maximum sum if needed
        max_sum = max(max_sum, current_sum)

    return max_sum

def max_subarray_with_indices(nums):
    """
    Enhanced version of max_subarray that returns the subarray indices 
    along with the maximum sum.

    Args:
        nums (list of int): Input array of integers

    Returns:
        tuple: (max_sum, start_index, end_index)

    Example:
        >>> max_subarray_with_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4])
        (6, 3, 6)
    """
    # Handle empty input
    if not nums:
        raise ValueError("Input list cannot be empty")

    max_sum = current_sum = nums[0]
    max_start = max_end = start = 0

    for end in range(1, len(nums)):
        # Reset start if current_sum becomes negative
        if current_sum + nums[end] < nums[end]:
            start = end
            current_sum = nums[end]
        else:
            current_sum += nums[end]

        # Update max_sum and indices if current_sum is larger
        if current_sum > max_sum:
            max_sum = current_sum
            max_start = start
            max_end = end

    return max_sum, max_start, max_end

Applies the simulated annealing algorithm to search for an optimal solution in a large search space.

Fri, 28 Mar 2025 03:37:16 +0000

# Simulated Annealing - Optimization Heuristic
# Description: Applies the simulated annealing algorithm to search for an optimal solution in a large search space.

import random
import math

def simulated_annealing(
    initial_state, 
    evaluate, 
    neighbor, 
    temperature=1000, 
    cooling_rate=0.995, 
    min_temp=0.1, 
    max_iterations=1000
):
    """
    Simulated Annealing: An optimization algorithm inspired by metallurgy.

    This algorithm explores a search space by probabilistically accepting 
    worse solutions to escape local optima, with decreasing probability 
    as the "temperature" cools down.

    Args:
        initial_state (any): Starting point in the search space.
        evaluate (function): Measures the quality of a state (cost function).
            Lower cost is considered better.
        neighbor (function): Generates a nearby alternative state.
        temperature (float): Initial exploration intensity.
        cooling_rate (float): Rate of reducing exploration probability.
        min_temp (float): Stopping temperature threshold.
        max_iterations (int): Limit on total iterations to prevent infinite loops.

    Returns:
        tuple: (best_state, best_cost) found during the search.

    Key Characteristics:
    - Probabilistically accepts worse solutions early on
    - Becomes more selective as temperature decreases
    - Helps escape local optima in complex search spaces

    Time Complexity: O(max_iterations)
    Space Complexity: O(1)
    """
    # Initialize the current state and its evaluation
    current_state = initial_state
    best_state = current_state
    current_cost = evaluate(current_state)
    best_cost = current_cost

    # Track iterations to prevent potential infinite loops
    iterations = 0

    # Simulated annealing main loop
    while temperature > min_temp and iterations < max_iterations:
        # Generate a neighboring state
        candidate_state = neighbor(current_state)
        candidate_cost = evaluate(candidate_state)

        # Calculate the cost difference
        cost_delta = candidate_cost - current_cost

        # Determine if we should accept the new state
        # Accept better states unconditionally
        # Accept worse states with decreasing probability
        if (cost_delta < 0 or 
            random.random() < math.exp(-cost_delta / temperature)):
            current_state = candidate_state
            current_cost = candidate_cost

            # Update the best state if needed
            if current_cost < best_cost:
                best_state = current_state
                best_cost = current_cost

        # Cool down the temperature
        temperature *= cooling_rate
        iterations += 1

    return best_state, best_cost

# Helpful example of how to use the algorithm
def example_usage():
    """
    Example demonstrating simulated annealing for finding 
    a near-optimal solution in a simple problem space.
    """
    def target_sum_evaluate(state):
        """Evaluate how close the sum is to a target value."""
        target = 15
        return abs(sum(state) - target)

    def neighbor_generator(state):
        """Generate a neighboring state by slightly modifying one element."""
        new_state = state.copy()
        index = random.randint(0, len(state) - 1)
        new_state[index] += random.randint(-2, 2)
        return new_state

    # Initial random state
    initial_state = [random.randint(1, 5) for _ in range(3)]

    # Run simulated annealing
    best_solution, best_cost = simulated_annealing(
        initial_state, 
        target_sum_evaluate, 
        neighbor_generator
    )

    print(f"Best Solution: {best_solution}")
    print(f"Best Cost: {best_cost}")

Approximates a minimum Steiner tree by greedily connecting terminals with the shortest edges.

Fri, 28 Mar 2025 03:37:09 +0000

# Steiner Tree - Greedy Approach (Not Optimal)
# Description: Approximates a minimum Steiner tree by greedily connecting terminals with the shortest edges.

def steiner_tree(graph, terminals):
    """
    Approximates the Steiner Tree using a greedy approach.

    This algorithm connects terminal nodes by repeatedly adding the shortest 
    edge that connects an existing tree node to a new node.

    Args:
        graph (dict): Adjacency list representation with edge weights.
        terminals (list): Nodes that must be included in the final tree.

    Returns:
        set: Nodes in the approximated Steiner tree.

    Time Complexity: O(V^2), where V is the number of vertices
    Space Complexity: O(V)

    Note: This is a greedy approximation and may not find the optimal Steiner tree.
    """
    # Initialize the tree with terminal nodes
    tree = set(terminals)

    # Iteratively expand the tree by adding the shortest connecting edge
    while len(tree) < len(graph):
        # Find the shortest edge connecting the current tree to a new node
        shortest_edge = None
        min_distance = float('inf')

        # Check edges from each node in the current tree
        for current_node in tree:
            for neighbor, distance in graph[current_node].items():
                # Find the shortest edge to a node not yet in the tree
                if neighbor not in tree and distance < min_distance:
                    shortest_edge = (current_node, neighbor)
                    min_distance = distance

        # If no connecting edge is found, break the loop
        if shortest_edge is None:
            break

        # Add the new node to the tree
        tree.add(shortest_edge[1])

    return tree

Attempts to find a subset of numbers that sums exactly to a target value using a greedy strategy.

Fri, 28 Mar 2025 03:36:59 +0000

# Subset Sum - Greedy Approach (Not Guaranteed Optimal)
# Description: Attempts to find a subset of numbers that sums exactly to a target value using a greedy strategy.

def subset_sum(nums, target):
    """
    Find a subset of numbers that sum exactly to the target using a greedy approach.

    This algorithm attempts to construct a subset by selecting numbers 
    in a way that approaches the target sum. It is not guaranteed to find 
    a solution even if one exists, due to its greedy nature.

    Args:
        nums (list of int): List of available numbers to select from.
        target (int): The desired total sum.

    Returns:
        list or str: A subset that sums to the target, or "No solution" if not found.

    Key Characteristics:
    - Sorts numbers in descending order to prioritize larger numbers
    - Greedily selects numbers that don't exceed the target
    - Not guaranteed to find a solution for all possible inputs

    Time Complexity: O(n log n) due to sorting
    Space Complexity: O(n)

    Note: This is an approximation and may not work for all subset sum instances.
    """
    # Check for invalid or impossible inputs
    if target < 0 or not nums:
        return "No solution"

    # Sort numbers in descending order to prioritize larger numbers
    sorted_nums = sorted(nums, reverse=True)

    # Attempt to construct a subset
    current_subset = []
    current_sum = 0

    # Greedily select numbers that don't exceed the target
    for num in sorted_nums:
        # If adding the current number doesn't exceed the target, include it
        if current_sum + num <= target:
            current_subset.append(num)
            current_sum += num

        # Early exit if exact target is reached
        if current_sum == target:
            return current_subset

    # Check if an exact solution was found
    return current_subset if current_sum == target else "No solution"

# Alternative implementation demonstrating multiple approaches
def subset_sum_advanced(nums, target):
    """
    A more comprehensive subset sum solver with multiple strategies.

    This version demonstrates additional handling and can be extended 
    to include more sophisticated search strategies.

    Args:
        nums (list of int): List of available numbers.
        target (int): Desired total sum.

    Returns:
        list or str: Solutions found through different methods.
    """
    def backtrack(index, current_subset, current_sum):
        # Found a valid subset
        if current_sum == target:
            return current_subset

        # Exceeded target or reached end of numbers
        if current_sum > target or index >= len(nums):
            return None

        # Try including the current number
        with_current = backtrack(
            index + 1, 
            current_subset + [nums[index]], 
            current_sum + nums[index]
        )
        if with_current:
            return with_current

        # Try excluding the current number
        without_current = backtrack(
            index + 1, 
            current_subset, 
            current_sum
        )
        return without_current

    result = backtrack(0, [], 0)    
    return result if result else "No solution"

# Demonstration function
def demonstrate_subset_sum():
    """
    Demonstrate subset sum solving with various inputs.
    """
    test_cases = [
        ([1, 2, 3, 4, 5, 6], 10),   # Possible solution
        ([7, 3, 2, 5], 15),          # Another test case
        ([100, 200, 300], 50)        # Impossible case
    ]

    for nums, target in test_cases:
        print(f"\nTesting nums={nums}, target={target}")
        print("Greedy Approach:", subset_sum(nums, target))
        print("Advanced Approach:", subset_sum_advanced(nums, target))

Recursively finds a TSP path by always visiting the nearest unvisited city, and finally returning to the start.

Fri, 28 Mar 2025 03:36:47 +0000

# TSP Greedy Recursive
# Description: Recursively finds a TSP path by always visiting the nearest unvisited city, and finally returning to the start.

def find_nearest_unvisited_city(current_city, dist, visited):
    """
    Find the nearest unvisited city from the current city.

    Args:
        current_city (int): Index of the current city
        dist (list of list): Distance matrix
        visited (list): Boolean array tracking visited cities

    Returns:
        int or None: Index of the nearest unvisited city, or None if all cities visited
    """
    nearest_city = None
    shortest_distance = float('inf')

    for city in range(len(dist)):
        if not visited[city] and dist[current_city][city] < shortest_distance:
            shortest_distance = dist[current_city][city]
            nearest_city = city

    return nearest_city

def tsp_greedy_recursive(dist):
    """
    Solve the Traveling Salesman Problem using a greedy recursive approach.

    Finds a route by always visiting the nearest unvisited city and 
    returning to the starting point. This is a heuristic approach 
    that does not guarantee the optimal solution.

    Args:
        dist (list of list): Distance matrix where dist[i][j] 
                              represents the distance from city i to city j

    Returns:
        list: Route (list of city indices) representing the greedy TSP path

    Example:
        distances = [
            [0, 10, 15, 20],
            [10, 0, 35, 25],
            [15, 35, 0, 30],
            [20, 25, 30, 0]
        ]
        route = tsp_greedy_recursive(distances)
        # Possible output: [0, 1, 3, 2, 0]
    """
    def recursive_tsp_helper(current_city, visited, route):
        """
        Recursive helper function to build the TSP route.

        Args:
            current_city (int): Current city being visited
            visited (list): Boolean array tracking visited cities
            route (list): Current route of cities

        Returns:
            list: Complete route including return to start
        """
        # Mark current city as visited and add to route
        visited[current_city] = True
        route.append(current_city)

        # Find the nearest unvisited city
        next_city = find_nearest_unvisited_city(current_city, dist, visited)

        # If no unvisited cities remain, return to start
        if next_city is None:
            route.append(route[0])
            return route

        # Recursively continue the route
        return recursive_tsp_helper(next_city, visited, route)

    # Initialize tracking for visited cities and route
    num_cities = len(dist)
    visited = [False] * num_cities
    route = []

    # Start the recursive TSP from city 0
    return recursive_tsp_helper(0, visited, route)

Schedule jobs on a fixed number of machines to minimize total completion time.

Fri, 28 Mar 2025 03:36:38 +0000

# Job Scheduling - Greedy Approach
# Description: Schedules jobs on a fixed number of machines to minimize total completion time by assigning each job to the machine with the least current load.

# Job Scheduling - Greedy Load Balancing Algorithm
def schedule_jobs(jobs, num_machines):
    """
    Distribute jobs across machines to minimize total completion time.

    The algorithm uses a greedy approach to balance workload:
    1. Sort jobs in descending order to prioritize larger jobs
    2. Assign each job to the least loaded machine

    Args:
        jobs (list of int): Duration of each job to be scheduled
        num_machines (int): Number of available machines to distribute jobs

    Returns:
        list of int: Total load on each machine after job assignment

    Time Complexity: O(n log n + n * m)
    Space Complexity: O(m), where n is number of jobs, m is number of machines

    Example:
        # Distribute 5 jobs across 3 machines
        >>> schedule_jobs([10, 15, 20, 25, 30], 3)
        [40, 40, 40]
    """
    # Validate input
    if not jobs or num_machines <= 0:
        return []

    # Sort jobs in descending order to optimize load balancing
    sorted_jobs = sorted(jobs, reverse=True)

    # Initialize machine loads
    machine_loads = [0] * num_machines

    # Assign each job to the least loaded machine
    for job in sorted_jobs:
        # Find the machine with minimum current load
        min_load_index = machine_loads.index(min(machine_loads))

        # Add job to the least loaded machine
        machine_loads[min_load_index] += job

    return machine_loads

# Demonstration of job scheduling
def demonstrate_job_scheduling():
    """
    Demonstrate the job scheduling algorithm with sample inputs.
    """
    # Test case 1: Even distribution
    jobs1 = [10, 15, 20, 25, 30]
    machines1 = 3
    print(f"Jobs {jobs1} on {machines1} machines:")
    print(schedule_jobs(jobs1, machines1))

    # Test case 2: Uneven job distribution
    jobs2 = [5, 8, 12, 13, 16, 20, 25, 30]
    machines2 = 4
    print(f"\nJobs {jobs2} on {machines2} machines:")
    print(schedule_jobs(jobs2, machines2))

Given a matrix and route, function improves route using 2-opt heuristic: reverses segments, reduce total travel distance.

Fri, 28 Mar 2025 03:36:31 +0000

# Traveling Salesman Problem - 2-Opt Heuristic
# Description: Given a distance matrix and an initial route, this function improves the route using the 2-opt heuristic by reversing segments to reduce the total travel distance.

# Traveling Salesman Problem (TSP) - 2-Opt Heuristic Optimization
def calculate_route_distance(route, distance_matrix):
    """
    Calculate the total distance of a route, including return to the starting city.

    Args:
        route (list of int): Ordered list of city indices
        distance_matrix (list of list of float): Matrix of distances between cities

    Returns:
        float: Total route distance
    """
    total_distance = 0
    route_length = len(route)

    # Sum distances between consecutive cities
    for i in range(route_length - 1):
        total_distance += distance_matrix[route[i]][route[i + 1]]

    # Add distance from last city back to first city (complete the tour)
    total_distance += distance_matrix[route[-1]][route[0]]

    return total_distance

def tsp_2opt(initial_route, distance_matrix, max_iterations=100):
    """
    Optimize a TSP route using the 2-opt heuristic algorithm.

    The 2-opt algorithm improves a route by:
    1. Selecting two edges in the current route
    2. Removing these edges
    3. Reconnecting the route in a different way
    4. Keeping the change if it reduces total route distance

    Args:
        initial_route (list of int): Starting route of city indices
        distance_matrix (list of list of float): Distances between cities
        max_iterations (int, optional): Maximum number of optimization iterations

    Returns:
        tuple: (optimized_route, total_distance)

    Time Complexity: O(n^3), where n is the number of cities
    Space Complexity: O(n)
    """
    # Validate inputs
    if not initial_route or len(initial_route) < 3:
        return initial_route, calculate_route_distance(initial_route, distance_matrix)

    # Current best solution
    best_route = initial_route.copy()
    best_distance = calculate_route_distance(best_route, distance_matrix)

    # Track improvement flag
    improved = True
    iterations = 0

    # Continue until no improvement or max iterations reached
    while improved and iterations < max_iterations:
        improved = False

        # Try all possible 2-opt swaps
        for i in range(1, len(best_route) - 1):
            for j in range(i + 1, len(best_route)):
                # Create a new route by reversing the segment between i and j
                new_route = (
                    best_route[:i] +  # Cities before swap point
                    best_route[i:j+1][::-1] +  # Reversed segment
                    best_route[j+1:]  # Cities after swap point
                )

                # Calculate new route distance
                new_distance = calculate_route_distance(new_route, distance_matrix)

                # Update if improved
                if new_distance < best_distance:
                    best_route = new_route
                    best_distance = new_distance
                    improved = True
                    break

            # Exit outer loop if improvement found
            if improved:
                break

        iterations += 1

    return best_route, best_distance

# Demonstration function
def demonstrate_tsp_2opt():
    """
    Demonstrate the 2-opt TSP optimization with sample distance matrix.
    """
    # Example distance matrix (symmetric)
    distance_matrix = [
        [0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]
    ]

    # Initial route
    initial_route = [0, 1, 2, 3]

    print("Initial Route:")
    print(f"Route: {initial_route}")
    print(f"Distance: {calculate_route_distance(initial_route, distance_matrix)}")

    # Optimize route
    optimized_route, optimized_distance = tsp_2opt(initial_route, distance_matrix)

    print("\nOptimized Route:")
    print(f"Route: {optimized_route}")
    print(f"Distance: {optimized_distance}")

Places N queens on an NxN chessboard so that no two queens threaten each other.

Fri, 28 Mar 2025 03:36:17 +0000

# N-Queens Problem - Backtracking
# Description: Places N queens on an NxN chessboard so that no two queens threaten each other.

# N-Queens Problem: Backtracking Solution
def solve_n_queens(n):
    """
    Solve the N-Queens problem by finding all possible ways to place N queens 
    on an NxN chessboard without any queens threatening each other.

    Args:
        n (int): Size of the chessboard and number of queens.

    Returns:
        list: All valid queen configurations, where each configuration is 
              represented by a list of column positions for each row.

    Time Complexity: O(N!)
    Space Complexity: O(N)
    """
    def is_queen_safe(board, current_row, current_col):
        """
        Check if placing a queen at the given position conflicts with existing queens.

        Args:
            board (list): Current board configuration
            current_row (int): Row of the new queen
            current_col (int): Column of the new queen

        Returns:
            bool: True if queen placement is safe, False otherwise
        """
        # Check for queens in the same column and diagonals
        for row in range(current_row):
            # Same column check
            if board[row] == current_col:
                return False

            # Diagonal conflict check (using absolute value)
            column_diff = abs(board[row] - current_col)
            row_diff = current_row - row
            if column_diff == row_diff:
                return False

        return True

    def place_queens(board, current_row):
        """
        Recursively place queens on the board using backtracking.

        Args:
            board (list): Current board configuration
            current_row (int): Current row being processed

        Modifies:
            solutions (list): Stores all valid board configurations
        """
        # Base case: all queens are placed successfully
        if current_row == n:
            solutions.append(board.copy())
            return

        # Try placing queen in each column of the current row
        for col in range(n):
            if is_queen_safe(board, current_row, col):
                # Place queen
                board[current_row] = col

                # Recursively place queens in next row
                place_queens(board, current_row + 1)

                # Backtrack (optional step in Python, but good for clarity)
                board[current_row] = -1

    # Initialize solution storage and board
    solutions = []
    initial_board = [-1] * n

    # Start the queen placement process
    place_queens(initial_board, 0)

    return solutions

Solves a standard 9x9 Sudoku puzzle ensuring that each row, column, and 3x3 subgrid contains numbers 1-9.

Fri, 28 Mar 2025 03:35:57 +0000

# Sudoku Solver - Backtracking
# Description: Solves a standard 9x9 Sudoku puzzle ensuring that each row, column, and 3x3 subgrid contains numbers 1-9.

def is_valid_placement(board, row, col, num):
    """
    Check if it's valid to place a number in a specific cell.

    Args:
        board (list of list of int): 9x9 Sudoku grid
        row (int): Row index of the cell
        col (int): Column index of the cell
        num (int): Number to place in the cell

    Returns:
        bool: True if placement is valid, False otherwise
    """
    # Check row
    for x in range(9):
        if board[row][x] == num:
            return False

    # Check column
    for x in range(9):
        if board[x][col] == num:
            return False

    # Check 3x3 sub-grid
    start_row = row - row % 3
    start_col = col - col % 3
    for i in range(3):
        for j in range(3):
            if board[start_row + i][start_col + j] == num:
                return False

    return True

def find_empty_cell(board):
    """
    Find an empty cell in the Sudoku board.

    Args:
        board (list of list of int): 9x9 Sudoku grid

    Returns:
        tuple or None: (row, col) of the first empty cell, or None if no empty cell exists
    """
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                return row, col
    return None

def solve_sudoku(board):
    """
    Solve a Sudoku puzzle using backtracking algorithm.

    This solver modifies the board in-place. It tries to fill empty cells 
    with numbers 1-9 while maintaining Sudoku rules.

    Time Complexity: O(9^(n*n)), where n is board size (9 in standard Sudoku)
    Space Complexity: O(n*n) due to recursion stack

    Args:
        board (list of list of int): 9x9 Sudoku grid 
                                     (0 represents empty cells)

    Returns:
        bool: True if a solution is found, False otherwise

    Example:
        board = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9]
        ]
        solve_sudoku(board)  # Solves the board in-place
    """
    # Find an empty cell
    empty_cell = find_empty_cell(board)

    # If no empty cell, puzzle is solved
    if not empty_cell:
        return True

    row, col = empty_cell

    # Try placing numbers 1-9
    for num in range(1, 10):
        # Check if number can be placed
        if is_valid_placement(board, row, col, num):
            # Place the number
            board[row][col] = num

            # Recursively try to solve the rest of the board
            if solve_sudoku(board):
                return True

            # If placement doesn't lead to solution, backtrack
            board[row][col] = 0

    # No solution found
    return False

def print_sudoku(board):
    """
    Print the Sudoku board in a readable format.

    Args:
        board (list of list of int): 9x9 Sudoku grid
    """
    for i, row in enumerate(board):
        # Print horizontal separators for 3x3 sub-grids
        if i % 3 == 0 and i != 0:
            print("-" * 21)

        for j, num in enumerate(row):
            # Print vertical separators for 3x3 sub-grids
            if j % 3 == 0 and j != 0:
                print("|", end=" ")
            print(num, end=" ")
        print()  # New line after each row