algorithms/backtrack.py

"""
USSU Algorithm Analyzer v4.0 - Backtracking & Branch-Bound Suite
N-Queens, Sudoku, Subset Sum, Graph Coloring, Hamiltonian Path.
"""
from typing import List, Dict, Tuple, Optional, Set
from utils.core import profile_algorithm, OperationCounter


class BacktrackingAlgorithms(OperationCounter):
    """Backtracking and Branch & Bound algorithm collection"""

    def __init__(self):
        super().__init__()
        self.solutions = []
        self.state_tree = []

    def reset(self):
        self.reset_counters()
        self.solutions = []
        self.state_tree = []

    # ==================== N-QUEENS ====================
    @profile_algorithm
    def n_queens(self, n: int = 8) -> Dict:
        self.reset()
        board = [[0] * n for _ in range(n)]
        solutions = []

        def is_safe(row, col):
            self.comparisons += 1
            for i in range(col):
                if board[row][i] == 1:
                    return False
            for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
                if board[i][j] == 1:
                    return False
            for i, j in zip(range(row, n, 1), range(col, -1, -1)):
                if board[i][j] == 1:
                    return False
            return True

        def solve(col):
            self.recursions += 1
            if col >= n:
                sol = [row[:] for row in board]
                solutions.append(sol)
                return True
            res = False
            for i in range(n):
                self.iterations += 1
                if is_safe(i, col):
                    board[i][col] = 1
                    res = solve(col + 1) or res
                    board[i][col] = 0
            return res

        solve(0)
        return {
            'algorithm': 'N-Queens (Backtracking)',
            'n': n,
            'solutions_found': len(solutions),
            'first_solution': solutions[0] if solutions else None,
            'time_complexity': 'O(n!)',
            'space_complexity': 'O(n²)',
            'recursions': self.recursions,
            'comparisons': self.comparisons,
        }

    # ==================== SUDOKU SOLVER ====================
    @profile_algorithm
    def sudoku_solver(self, grid: List[List[int]]) -> Dict:
        self.reset()
        n = len(grid)
        sqrt_n = int(n ** 0.5)

        def is_valid(row, col, num):
            self.comparisons += 1
            for x in range(n):
                if grid[row][x] == num or grid[x][col] == num:
                    return False
            start_row, start_col = row - row % sqrt_n, col - col % sqrt_n
            for i in range(sqrt_n):
                for j in range(sqrt_n):
                    if grid[i + start_row][j + start_col] == num:
                        return False
            return True

        def solve():
            self.recursions += 1
            for i in range(n):
                for j in range(n):
                    if grid[i][j] == 0:
                        for num in range(1, n + 1):
                            self.iterations += 1
                            if is_valid(i, j, num):
                                grid[i][j] = num
                                if solve():
                                    return True
                                grid[i][j] = 0
                        return False
            return True

        solved = solve()
        return {
            'algorithm': 'Sudoku Solver (Backtracking)',
            'solved': solved,
            'grid': grid,
            'time_complexity': 'O(9^(n²)) worst',
            'space_complexity': 'O(n²)',
            'recursions': self.recursions,
            'comparisons': self.comparisons,
        }

    # ==================== SUBSET SUM ====================
    @profile_algorithm
    def subset_sum(self, arr: List[int], target: int) -> Dict:
        self.reset()
        n = len(arr)
        result = []

        def find_subsets(index, current, current_sum):
            self.recursions += 1
            if current_sum == target:
                result.append(current[:])
                return
            if index >= n or current_sum > target:
                return
            self.iterations += 1
            current.append(arr[index])
            find_subsets(index + 1, current, current_sum + arr[index])
            current.pop()
            find_subsets(index + 1, current, current_sum)

        find_subsets(0, [], 0)
        return {
            'algorithm': 'Subset Sum (Backtracking)',
            'target': target,
            'subsets': result,
            'count': len(result),
            'time_complexity': 'O(2ⁿ)',
            'space_complexity': 'O(n)',
            'recursions': self.recursions,
        }

    # ==================== GRAPH COLORING ====================
    @profile_algorithm
    def graph_coloring(self, adj: List[List[int]], m: int) -> Dict:
        self.reset()
        n = len(adj)
        colors = [0] * n

        def is_safe(v, c):
            self.comparisons += 1
            for i in range(n):
                if adj[v][i] == 1 and colors[i] == c:
                    return False
            return True

        def solve(v):
            self.recursions += 1
            if v == n:
                return True
            for c in range(1, m + 1):
                self.iterations += 1
                if is_safe(v, c):
                    colors[v] = c
                    if solve(v + 1):
                        return True
                    colors[v] = 0
            return False

        possible = solve(0)
        return {
            'algorithm': 'Graph Coloring (Backtracking)',
            'colors_needed': max(colors) if possible else 0,
            'coloring': colors if possible else [],
            'possible': possible,
            'time_complexity': 'O(m^V)',
            'space_complexity': 'O(V)',
            'recursions': self.recursions,
            'comparisons': self.comparisons,
        }

    # ==================== HAMILTONIAN CYCLE ====================
    @profile_algorithm
    def hamiltonian_cycle(self, adj: List[List[int]], start: int = 0) -> Dict:
        self.reset()
        n = len(adj)
        path = [-1] * n
        path[0] = start

        def is_safe(v, pos):
            self.comparisons += 1
            if adj[path[pos - 1]][v] == 0:
                return False
            for i in range(pos):
                if path[i] == v:
                    return False
            return True

        def solve(pos):
            self.recursions += 1
            if pos == n:
                return adj[path[pos - 1]][start] == 1
            for v in range(n):
                self.iterations += 1
                if is_safe(v, pos):
                    path[pos] = v
                    if solve(pos + 1):
                        return True
                    path[pos] = -1
            return False

        found = solve(1)
        return {
            'algorithm': 'Hamiltonian Cycle (Backtracking)',
            'cycle': path + [start] if found else [],
            'found': found,
            'time_complexity': 'O((V-1)!)',
            'space_complexity': 'O(V)',
            'recursions': self.recursions,
            'comparisons': self.comparisons,
        }