Impact of Pruning

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

"""
Demonstrating the quantitative impact of pruning on search tree exploration.
 
This module shows how pruning at different depths affects the total
number of nodes explored, and why early pruning is exponentially better.
"""
 
def analyze_pruning_impact(depth: int, branching_factor: int = 2):
    """
    Analyze the impact of pruning at different depths in a uniform tree.
    
    Parameters:
    - depth: Total depth of the tree
    - branching_factor: Number of children per node
    """
    b, d = branching_factor, depth
    
    # Total nodes without pruning
    total_nodes = (b**(d + 1) - 1) // (b - 1)
    total_leaves = b**d
    
    print(f"Tree: depth={d}, branching={b}")
    print(f"Total nodes without pruning: {total_nodes:,}")
    print(f"Total leaves without pruning: {total_leaves:,}")
    print()
    
    print("Impact of pruning ONE node at each depth:")
    print("-" * 55)
    print(f"{'Depth':>6} | {'Subtree Size':>12} | {'Leaves Saved':>12} | {'% Saved':>10}")
    print("-" * 55)
    
    for prune_depth in range(d + 1):
        # Subtree rooted at depth prune_depth has depth (d - prune_depth)
        subtree_depth = d - prune_depth
        subtree_leaves = b**subtree_depth
        subtree_nodes = (b**(subtree_depth + 1) - 1) // (b - 1)
        pct_saved = 100 * subtree_leaves / total_leaves
        
        print(f"{prune_depth:>6} | {subtree_nodes:>12,} | "
              f"{subtree_leaves:>12,} | {pct_saved:>9.2f}%")
    
    return {
        'total_nodes': total_nodes,
        'total_leaves': total_leaves,
        'depth': d,
        'branching': b
    }
 
 
def compare_pruning_scenarios():
    """
    Compare scenarios with different pruning effectiveness.
    """
    print("
" + "=" * 70)
    print("PRUNING EFFECTIVENESS COMPARISON")
    print("=" * 70)
    
    # Scenario: Binary tree of depth 20 (2^20 ≈ 1 million leaves)
    d = 20
    b = 2
    total_leaves = b**d
    
    scenarios = [
        ("No pruning", 0, total_leaves),
        ("Prune 50% at depth 1", 1, total_leaves // 2),
        ("Prune 75% at depth 2", 2, total_leaves // 4),
        ("Prune 99% at depth 5", 5, total_leaves // 100),
        ("Prune 99.9% at depth 10", 10, total_leaves // 1000),
    ]
    
    print(f"
Base: Binary tree of depth {d} ({total_leaves:,} leaves)")
    print()
    
    for name, _, remaining in scenarios:
        pct_explored = 100 * remaining / total_leaves
        print(f"  {name:30s}: {remaining:>12,} leaves ({pct_explored:>6.2f}%)")
    
    print()
    print("Key insight: Even modest pruning rates create massive savings.")
    print("99% pruning sounds aggressive, but it still explores 10,000+ leaves!")
 
 
def demonstrate_constraint_pruning():
    """
    Show how N-Queens pruning works at each constraint level.
    """
    print("
" + "=" * 70)
    print("N-QUEENS CONSTRAINT PRUNING BREAKDOWN (n=8)")
    print("=" * 70)
    
    def count_with_constraint_levels(n: int):
        # Level 0: No constraints
        level0_naive = n**n
        
        # Level 1: One queen per row (already implicit in row-by-row)
        level1_per_row = n**n  # Same, just reorganized
        
        # Level 2: One queen per column
        import math
        level2_per_col = math.factorial(n)
        
        # Level 3: Diagonal constraints (actual exploration)
        nodes_explored = 0
        solutions = 0
        
        def solve(row, cols, diag1, diag2):
            nonlocal nodes_explored, solutions
            nodes_explored += 1
            if row == n:
                solutions += 1
                return
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                solve(row + 1, cols, diag1, diag2)
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
        
        solve(0, set(), set(), set())
        
        return {
            'naive': level0_naive,
            'column_only': level2_per_col,
            'all_constraints': nodes_explored,
            'solutions': solutions
        }
    
    n = 8
    result = count_with_constraint_levels(n)
    
    levels = [
        ("Naive (n^n, no constraints)", result['naive']),
        ("Column constraint (n!)", result['column_only']),
        ("All constraints (actual)", result['all_constraints']),
        ("Valid solutions", result['solutions']),
    ]
    
    print(f"
For {n}-Queens problem:
")
    base = levels[0][1]
    for name, count in levels:
        pct = 100 * count / base
        reduction = base / count if count > 0 else float('inf')
        print(f"  {name:35s}: {count:>12,} ({pct:>8.4f}%, {reduction:>10.1f}x reduction)")
    
    print(f"
Column pruning alone gives {result['naive']/result['column_only']:.0f}x reduction")
    print(f"Diagonal pruning adds another {result['column_only']/result['all_constraints']:.1f}x reduction")
 
 
# Run demonstrations
analyze_pruning_impact(10, 2)
compare_pruning_scenarios()
demonstrate_constraint_pruning()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

"""
Metrics for quantifying pruning effectiveness in backtracking algorithms.
 
These metrics help compare different algorithms and understand
where optimization efforts should be focused.
"""
 
import math
from typing import Callable
 
def calculate_pruning_metrics(
    theoretical_size: int,
    actual_explored: int,
    depth: int
) -> dict:
    """
    Calculate comprehensive pruning metrics.
    
    Parameters:
    - theoretical_size: Size of unpruned tree (all leaves)
    - actual_explored: Actual nodes visited during search
    - depth: Tree depth (number of decision levels)
    """
    # Pruning factor
    pruning_factor = theoretical_size / actual_explored if actual_explored > 0 else float('inf')
    
    # Effective branching factor: b* such that b*^d ≈ actual_explored
    if actual_explored > 1 and depth > 0:
        effective_b = actual_explored ** (1.0 / depth)
    else:
        effective_b = 1.0
    
    # Pruning rate: percentage of nodes pruned
    pruning_rate = 1.0 - (actual_explored / theoretical_size) if theoretical_size > 0 else 0
    
    # Log reduction (how many orders of magnitude)
    log_reduction = math.log10(pruning_factor) if pruning_factor > 1 else 0
    
    return {
        'theoretical_size': theoretical_size,
        'actual_explored': actual_explored,
        'depth': depth,
        'pruning_factor': pruning_factor,
        'effective_branching_factor': effective_b,
        'pruning_rate': pruning_rate,
        'log_reduction': log_reduction
    }
 
 
def compare_algorithms_by_metrics():
    """
    Compare pruning effectiveness across different algorithms.
    """
    print("=" * 80)
    print("PRUNING METRICS COMPARISON")
    print("=" * 80)
    
    algorithms = [
        # (name, theoretical_leaves, actual_nodes, depth)
        ("Subset generation (n=15)", 2**15, 2**16 - 1, 15),  # No pruning
        ("Subset sum (n=15, tight target)", 2**15, 5000, 15),  # Medium pruning
        ("N-Queens (n=8)", 8**8, 2057, 8),
        ("N-Queens (n=10)", 10**10, 9965, 10),
        ("N-Queens (n=12)", 12**12, 45805, 12),
        ("Sudoku (typical)", 9**81, 1000, 81),  # Heavy pruning approximation
    ]
    
    print()
    print(f"{'Algorithm':35s} | {'Theory':>12} | {'Actual':>10} | "
          f"{'Factor':>10} | {'b*':>5} | {'OoM':>5}")
    print("-" * 90)
    
    for name, theory, actual, depth in algorithms:
        metrics = calculate_pruning_metrics(theory, actual, depth)
        
        # Format large numbers
        theory_str = f"{theory:.2e}" if theory > 1e6 else f"{theory:,}"
        actual_str = f"{actual:,}"
        factor_str = f"{metrics['pruning_factor']:.1e}" if metrics['pruning_factor'] > 1e6 else f"{metrics['pruning_factor']:.1f}"
        
        print(f"{name:35s} | {theory_str:>12} | {actual_str:>10} | "
              f"{factor_str:>10} | {metrics['effective_branching_factor']:>5.2f} | "
              f"{metrics['log_reduction']:>5.1f}")
    
    print()
    print("Legend:")
    print("  Theory = Theoretical tree size without pruning")
    print("  Actual = Nodes actually explored")
    print("  Factor = Pruning factor (Theory/Actual)")
    print("  b* = Effective branching factor")
    print("  OoM = Orders of magnitude reduction (log₁₀ of Factor)")
 
 
def measure_pruning_by_level(algorithm_func: Callable, n: int, description: str):
    """
    Measure which levels contribute most to pruning.
    
    This helps identify where to focus optimization efforts.
    """
    print(f"
{'=' * 60}")
    print(f"LEVEL-BY-LEVEL PRUNING ANALYSIS: {description}")
    print("=" * 60)
    
    # Instrument to count nodes at each level
    level_counts = {}
    
    # We'd need to modify the algorithm to track this
    # Placeholder showing the concept
    print("
(Concept: Track nodes explored at each recursion depth)")
    print("(Compare to theoretical: branching_factor^depth)")
    print("(Levels with biggest ratio = most effective pruning)")
 
 
def demonstrate_input_sensitivity():
    """
    Show how pruning effectiveness varies by input.
    """
    print("
" + "=" * 60)
    print("INPUT SENSITIVITY OF PRUNING")
    print("=" * 60)
    
    # Subset sum with different targets
    def subset_sum_nodes(elements: list, target: int) -> int:
        nodes = 0
        def backtrack(idx, current_sum):
            nonlocal nodes
            nodes += 1
            if idx == len(elements):
                return
            # Pruning: if current_sum already exceeds target, stop
            if current_sum > target:
                return
            # Exclude
            backtrack(idx + 1, current_sum)
            # Include
            backtrack(idx + 1, current_sum + elements[idx])
        backtrack(0, 0)
        return nodes
    
    elements = list(range(1, 21))  # [1, 2, ..., 20]
    theoretical = 2**20
    
    print(f"
Subset sum: elements=[1..20], theoretical tree = 2^20 = {theoretical:,}")
    print()
    print(f"{'Target':>10} | {'Nodes':>12} | {'Pruning Factor':>15} | {'Pruning Rate':>12}")
    print("-" * 60)
    
    for target in [10, 50, 100, 150, 200, 210]:
        nodes = subset_sum_nodes(elements, target)
        factor = theoretical / nodes
        rate = 1 - nodes / theoretical
        print(f"{target:>10} | {nodes:>12,} | {factor:>15.1f}x | {rate*100:>11.2f}%")
    
    print()
    print("Observation: Tight targets enable heavy pruning; loose targets prune less.")
 
 
# Run all demonstrations
compare_algorithms_by_metrics()
demonstrate_input_sensitivity()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216

"""
Examples of different pruning strategies and their implementations.
"""
 
from typing import List, Set, Optional
 
# ============================================
# FEASIBILITY PRUNING: Subset Sum
# ============================================
 
def subset_sum_with_pruning(nums: List[int], target: int) -> List[List[int]]:
    """
    Find all subsets that sum to target, with pruning.
    
    Pruning strategies:
    1. If current_sum > target, stop (for positive numbers)
    2. If current_sum + remaining_sum < target, stop
    """
    nums.sort()  # Sort to enable remaining_sum pruning
    results = []
    n = len(nums)
    
    # Precompute suffix sums for pruning
    suffix_sums = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_sums[i] = suffix_sums[i + 1] + nums[i]
    
    def backtrack(idx: int, current: List[int], current_sum: int):
        # Feasibility pruning 1: exceeded target
        if current_sum > target:
            return
        
        # Feasibility pruning 2: can't reach target even with all remaining
        if current_sum + suffix_sums[idx] < target:
            return
        
        if current_sum == target:
            results.append(current[:])
            return
        
        if idx >= n:
            return
        
        # Include nums[idx]
        current.append(nums[idx])
        backtrack(idx + 1, current, current_sum + nums[idx])
        current.pop()
        
        # Exclude nums[idx]
        backtrack(idx + 1, current, current_sum)
    
    backtrack(0, [], 0)
    return results
 
 
# ============================================
# BOUND PRUNING: Maximum Weight Path
# ============================================
 
def max_value_path_with_bound_pruning(
    graph: List[List[tuple]],  # Adjacency list: [(neighbor, value), ...]
    start: int,
    end: int
) -> int:
    """
    Find maximum value path from start to end with bound pruning.
    
    Uses optimistic bound: current_value + max_remaining
    """
    n = len(graph)
    best_value = float('-inf')
    
    # Optimistic estimate: sum of all edge values
    total_value = sum(val for edges in graph for _, val in edges)
    
    def backtrack(node: int, visited: Set[int], current_value: int):
        nonlocal best_value
        
        if node == end:
            best_value = max(best_value, current_value)
            return
        
        # Bound pruning: even if we got all remaining value, can we beat best?
        remaining_estimate = total_value - current_value  # Optimistic
        if current_value + remaining_estimate <= best_value:
            return  # PRUNE: can't possibly beat best
        
        for neighbor, value in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                backtrack(neighbor, visited, current_value + value)
                visited.remove(neighbor)
    
    backtrack(start, {start}, 0)
    return best_value
 
 
# ============================================
# SYMMETRY PRUNING: N-Queens
# ============================================
 
def n_queens_with_symmetry_pruning(n: int) -> int:
    """
    Count N-Queens solutions with symmetry breaking.
    
    Symmetry: 8-fold (4 rotations × 2 reflections for square board)
    
    Strategy: Only place first queen in left half of first row,
    then multiply by 2 for reflection symmetry.
    
    (Full symmetry handling is more complex but this captures the idea)
    """
    count = 0
    
    def backtrack(row: int, cols: Set[int], diag1: Set[int], diag2: Set[int]):
        nonlocal count
        if row == n:
            count += 1
            return
        
        # Symmetry pruning: restrict first row choices to left half
        col_range = range(n // 2 + 1) if row == 0 else range(n)
        
        for col in col_range:
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            backtrack(row + 1, cols, diag1, diag2)
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
    
    backtrack(0, set(), set(), set())
    
    # Multiply by 2 for reflection (simplified; full symmetry is more complex)
    return count * 2
 
 
# ============================================
# ORDERING HEURISTIC: Sudoku with MRV
# ============================================
 
def solve_sudoku_with_mrv(board: List[List[int]]) -> bool:
    """
    Solve Sudoku with Minimum Remaining Values (MRV) heuristic.
    
    MRV: Always fill the cell with fewest legal candidates first.
    This maximizes the chance of early pruning or failure detection.
    """
    def get_candidates(r: int, c: int) -> Set[int]:
        """Get legal values for cell (r, c)."""
        if board[r][c] != 0:
            return set()
        
        used = set()
        # Row
        for j in range(9):
            used.add(board[r][j])
        # Column
        for i in range(9):
            used.add(board[i][c])
        # Box
        br, bc = 3 * (r // 3), 3 * (c // 3)
        for i in range(br, br + 3):
            for j in range(bc, bc + 3):
                used.add(board[i][j])
        
        return set(range(1, 10)) - used
    
    def find_mrv_cell() -> Optional[tuple]:
        """Find empty cell with minimum remaining values (MRV heuristic)."""
        min_count = 10
        best_cell = None
        
        for r in range(9):
            for c in range(9):
                if board[r][c] == 0:
                    count = len(get_candidates(r, c))
                    if count == 0:
                        return None  # No candidates = dead end
                    if count < min_count:
                        min_count = count
                        best_cell = (r, c)
        
        return best_cell
    
    def backtrack() -> bool:
        cell = find_mrv_cell()
        if cell is None:
            # Check if solved or dead end
            return all(board[r][c] != 0 for r in range(9) for c in range(9))
        
        r, c = cell
        for val in get_candidates(r, c):
            board[r][c] = val
            if backtrack():
                return True
            board[r][c] = 0
        
        return False
    
    return backtrack()
 
 
# Demonstration
if __name__ == "__main__":
    print("Subset Sum with Pruning:")
    result = subset_sum_with_pruning([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15)
    print(f"  Found {len(result)} subsets summing to 15")
    
    print("
N-Queens with Symmetry Pruning (n=8):")
    count = n_queens_with_symmetry_pruning(8)
    print(f"  Found approximately {count} solutions (simplified symmetry)")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

"""
Analyzing whether a pruning optimization is worth implementing.
 
This module demonstrates how to decide if the overhead of a pruning
check is justified by the nodes it eliminates.
"""
 
import time
from typing import Callable, Tuple
 
def evaluate_pruning_strategy(
    algorithm_without: Callable[[], int],
    algorithm_with: Callable[[], int],
    iterations: int = 10
) -> dict:
    """
    Compare algorithm performance with and without a pruning strategy.
    
    Returns detailed analysis of whether the pruning helps.
    """
    # Measure without pruning
    times_without = []
    nodes_without = []
    for _ in range(iterations):
        start = time.perf_counter()
        nodes = algorithm_without()
        elapsed = time.perf_counter() - start
        times_without.append(elapsed)
        nodes_without.append(nodes)
    
    # Measure with pruning
    times_with = []
    nodes_with = []
    for _ in range(iterations):
        start = time.perf_counter()
        nodes = algorithm_with()
        elapsed = time.perf_counter() - start
        times_with.append(elapsed)
        nodes_with.append(nodes)
    
    # Compute statistics
    avg_time_without = sum(times_without) / len(times_without)
    avg_time_with = sum(times_with) / len(times_with)
    avg_nodes_without = sum(nodes_without) / len(nodes_without)
    avg_nodes_with = sum(nodes_with) / len(nodes_with)
    
    time_speedup = avg_time_without / avg_time_with if avg_time_with > 0 else float('inf')
    node_reduction = avg_nodes_without / avg_nodes_with if avg_nodes_with > 0 else float('inf')
    
    # Is the pruning worthwhile?
    worthwhile = time_speedup > 1.0
    
    return {
        'avg_time_without': avg_time_without,
        'avg_time_with': avg_time_with,
        'time_speedup': time_speedup,
        'avg_nodes_without': avg_nodes_without,
        'avg_nodes_with': avg_nodes_with,
        'node_reduction': node_reduction,
        'worthwhile': worthwhile,
        'summary': (
            f"Nodes: {node_reduction:.2f}x fewer, "
            f"Time: {time_speedup:.2f}x faster, "
            f"Verdict: {'WORTHWHILE' if worthwhile else 'NOT WORTH IT'}"
        )
    }
 
 
def demonstrate_cost_benefit():
    """
    Demonstrate a case where 'smart' pruning is actually slower.
    """
    print("=" * 70)
    print("PRUNING COST-BENEFIT ANALYSIS")
    print("=" * 70)
    
    # Simple counting to demonstrate overhead
    def count_without_optimization():
        """Simple counting without extra check."""
        count = 0
        for i in range(1000):
            for j in range(1000):
                count += 1
                # Simple work
                _ = i + j
        return count
    
    def count_with_expensive_check():
        """Same counting but with expensive 'optimization' that rarely helps."""
        count = 0
        skipped = 0
        for i in range(1000):
            for j in range(1000):
                count += 1
                # Expensive "optimization" check
                check_result = sum(range(100))  # Expensive!
                if check_result == 99999999:  # Never true
                    skipped += 1
                    continue
                _ = i + j
        return count - skipped
    
    def count_with_cheap_effective_check():
        """Counting with cheap check that actually helps."""
        count = 0
        for i in range(1000):
            if i % 2 == 0:  # Cheap check, skips 50%
                continue
            for j in range(1000):
                count += 1
                _ = i + j
        return count
    
    print("
Case 1: Expensive check that never triggers")
    print("-" * 50)
    result1 = evaluate_pruning_strategy(
        count_without_optimization,
        count_with_expensive_check,
        iterations=5
    )
    print(result1['summary'])
    
    print("
Case 2: Cheap check that skips 50%")
    print("-" * 50)
    result2 = evaluate_pruning_strategy(
        count_without_optimization,
        count_with_cheap_effective_check,
        iterations=5
    )
    print(result2['summary'])
 
 
# Run demonstration
demonstrate_cost_benefit()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

"""
Demonstrating input-dependent variance in backtracking performance.
 
The same algorithm can show dramatically different performance
on different inputs, even of the same size.
"""
 
import random
import statistics
from typing import List
 
def analyze_subset_sum_variance():
    """
    Show how subset sum runtime varies with target value.
    """
    print("=" * 60)
    print("SUBSET SUM PERFORMANCE VARIANCE")
    print("=" * 60)
    
    elements = list(range(1, 26))  # [1, 2, ..., 25]
    total_sum = sum(elements)  # 325
    theoretical_nodes = 2**25  # ~33 million
    
    def solve(target):
        nodes = [0]
        solutions = [0]
        
        def backtrack(idx, current_sum):
            nodes[0] += 1
            if current_sum > target:
                return
            if current_sum == target:
                solutions[0] += 1
            if idx >= len(elements):
                return
            # Exclude
            backtrack(idx + 1, current_sum)
            # Include
            backtrack(idx + 1, current_sum + elements[idx])
        
        backtrack(0, 0)
        return nodes[0], solutions[0]
    
    print(f"
Elements: 1 to 25, Total sum: {total_sum}")
    print(f"Theoretical tree size: 2^25 = {theoretical_nodes:,}")
    print()
    
    print(f"{'Target':>12} | {'Nodes':>12} | {'Solutions':>10} | {'Pruning':>10}")
    print("-" * 55)
    
    for target in [1, 10, 50, 100, 150, 200, 300, 325]:
        nodes, solutions = solve(target)
        pruning_pct = (1 - nodes / theoretical_nodes) * 100
        print(f"{target:>12} | {nodes:>12,} | {solutions:>10,} | {pruning_pct:>9.2f}%")
    
    print(f"
Variance: {1:,} to {sum(elements):,} target changes nodes by ~1000x!")
 
 
def analyze_nqueens_variance():
    """
    N-Queens has similar structure for all n, but some n values
    are 'harder' in terms of solution density and exploration.
    """
    print("
" + "=" * 60)
    print("N-QUEENS EXPLORATION VARIANCE BY N")
    print("=" * 60)
    
    import math
    
    def solve_nqueens(n):
        nodes = [0]
        solutions = [0]
        
        def backtrack(row, cols, d1, d2):
            nodes[0] += 1
            if row == n:
                solutions[0] += 1
                return
            for col in range(n):
                if col in cols or (row-col) in d1 or (row+col) in d2:
                    continue
                cols.add(col)
                d1.add(row-col)
                d2.add(row+col)
                backtrack(row+1, cols, d1, d2)
                cols.remove(col)
                d1.remove(row-col)
                d2.remove(row+col)
        
        backtrack(0, set(), set(), set())
        return nodes[0], solutions[0]
    
    print(f"
{'n':>3} | {'Nodes':>12} | {'Solutions':>10} | {'n!':>12} | {'Ratio':>8}")
    print("-" * 55)
    
    for n in range(4, 14):
        nodes, solutions = solve_nqueens(n)
        factorial = math.factorial(n)
        ratio = factorial / nodes
        print(f"{n:>3} | {nodes:>12,} | {solutions:>10,} | {factorial:>12,} | {ratio:>8.1f}x")
 
 
def demonstrate_pathological_input():
    """
    Show how certain input patterns defeat typical heuristics.
    """
    print("
" + "=" * 60)
    print("PATHOLOGICAL INPUT PATTERNS")
    print("=" * 60)
    
    # Example: Subset sum where all elements equal 1
    # This defeats the "prune if sum > target" heuristic
    
    def solve_subset_sum(elements, target):
        nodes = [0]
        def backtrack(idx, current_sum):
            nodes[0] += 1
            if current_sum > target:
                return
            if idx >= len(elements):
                return
            backtrack(idx + 1, current_sum)
            backtrack(idx + 1, current_sum + elements[idx])
        backtrack(0, 0)
        return nodes[0]
    
    print("
Subset sum with pruning 'if current_sum > target, stop':")
    print()
    
    # Good case: increasing elements
    good_elements = list(range(1, 21))  # [1, 2, ..., 20]
    good_nodes = solve_subset_sum(good_elements, 10)
    
    # Bad case: all ones (pruning rarely triggers)
    bad_elements = [1] * 20
    bad_nodes = solve_subset_sum(bad_elements, 10)
    
    print(f"  Good case [1,2,...,20], target=10: {good_nodes:>10,} nodes")
    print(f"  Bad case  [1,1,...,1], target=10:  {bad_nodes:>10,} nodes")
    print(f"  Ratio: {bad_nodes / good_nodes:.1f}x worse for 'bad' input")
    print()
    print("  Same algorithm, same n, but input structure matters!")
 
 
# Run all demonstrations
analyze_subset_sum_variance()
analyze_nqueens_variance()
demonstrate_pathological_input()