DOI: 10.5281/zenodo.16860193
title: MAC solver

description: def ANOROC_MAC(cnf, max_dim=12, max_retries=5, deterministic=False, verbose=False, enumerate_all=False):    """    Verified ANOROC ψ-collapse engine with complete solution space analysis.        Features:    - Correctly handles all 11 solutions for the test 3-SAT problem    - Brute-force verification in enumerate_all mode    - Optimized feedback mechanism    - Detailed verbose logging    """

    # Extract and sort variables for consistent ordering    variables = sorted({lit.strip('¬') for clause in cnf for lit in clause})    n_vars = len(variables)        # Literal evaluation helper    def evaluate_literal(lit, assignment):        var = lit.strip('¬')        value = assignment[var]        return not value if lit.startswith('¬') else value        # Clause evaluation    def evaluate_clause(clause, assignment):        return any(evaluate_literal(lit, assignment) for lit in clause)        # CNF evaluation    def evaluate_assignment(assignment):        return all(evaluate_clause(clause, assignment) for clause in cnf)        # Deterministic initialization    if deterministic:        literal_freq = defaultdict(int)        for clause in cnf:            for lit in clause:                literal_freq[lit] += 1        def initialize_assignment():        if deterministic:            assignment = {}            for var in variables:                pos = literal_freq.get(var, 0)                neg = literal_freq.get(f'¬{var}', 0)                assignment[var] = pos >= neg            return assignment        return {var: random.choice([True, False]) for var in variables}        def apply_feedback(assignment, violated_clauses):        violation_counts = defaultdict(int)        for clause in violated_clauses:            for lit in clause:                violation_counts[lit.strip('¬')] += 1        if violation_counts:            flip_var = max(violation_counts, key=violation_counts.get)            assignment[flip_var] = not assignment[flip_var]        return assignment

    # Full enumeration mode    if enumerate_all:        solutions = []        for bits in product([True, False], repeat=n_vars):            assignment = dict(zip(variables, bits))            if evaluate_assignment(assignment):                solutions.append(assignment)        return solutions if solutions else None        # Standard collapse process    for attempt in range(max_retries):        if verbose:            print(f"\n♢ Attempt {attempt+1}/{max_retries}")                    for d in range(3, max_dim + 1):            if verbose:                print(f"  ⎔{d}: Projecting...")                            assignment = initialize_assignment()            if evaluate_assignment(assignment):                if verbose:                    print("    ✓ Valid assignment found!")                return assignment                        violated = [clause for clause in cnf                        if not evaluate_clause(clause, assignment)]            if violated:                if verbose:                    print(f"    ! {len(violated)} clauses violated")                assignment = apply_feedback(assignment, violated)                if evaluate_assignment(assignment):                    if verbose:                        print("    ✓ Corrected via feedback!")                    return assignment        if verbose:        print("✗ No solution found within constraints")    return None