"""
Constraint Satisfaction Problem (CSP) Solver
Solve problems like Sudoku, scheduling, map coloring
"""
from typing import Dict, List, Set, Callable
import time

class CSP:
    """Constraint Satisfaction Problem"""
    
    def __init__(self, variables: List, domains: Dict, constraints: List):
        self.variables = variables
        self.domains = domains
        self.constraints = constraints
    
    def is_consistent(self, assignment: Dict, var, value) -> bool:
        """Check if assignment is consistent with constraints"""
        test_assignment = {**assignment, var: value}
        
        for constraint in self.constraints:
            if not constraint(test_assignment):
                return False
        return True
    
    def select_unassigned_variable(self, assignment: Dict):
        """MRV heuristic: choose variable with fewest legal values"""
        unassigned = [v for v in self.variables if v not in assignment]
        return min(unassigned, key=lambda v: len(self.domains[v]))
    
    def backtrack(self, assignment: Dict) -> Dict:
        """Backtracking search"""
        if len(assignment) == len(self.variables):
            return assignment
        
        var = self.select_unassigned_variable(assignment)
        
        for value in self.domains[var]:
            if self.is_consistent(assignment, var, value):
                result = self.backtrack({**assignment, var: value})
                if result is not None:
                    return result
        
        return None
    
    def solve(self) -> Dict:
        """Solve CSP"""
        return self.backtrack({})

def solve_sudoku_example():
    """Solve 4x4 Sudoku as CSP"""
    print("\n" + "="*70)
    print("CSP SOLVER: 4x4 SUDOKU")
    print("="*70)
    
    # 4x4 Sudoku puzzle (0 = empty)
    puzzle = [
        [1, 0, 0, 4],
        [0, 0, 1, 0],
        [0, 3, 0, 0],
        [4, 0, 0, 2]
    ]
    
    print("\nInitial puzzle:")
    for row in puzzle:
        print(' '.join(str(x) if x != 0 else '.' for x in row))
    
    # Create CSP
    variables = [(i, j) for i in range(4) for j in range(4) if puzzle[i][j] == 0]
    domains = {var: [1, 2, 3, 4] for var in variables}
    
    # Fixed values
    fixed = {(i, j): puzzle[i][j] for i in range(4) for j in range(4) if puzzle[i][j] != 0}
    
    def all_different(values):
        """Check all values are different"""
        non_zero = [v for v in values if v is not None]
        return len(non_zero) == len(set(non_zero))
    
    def row_constraint(assignment):
        """All values in row must be different"""
        full_assignment = {**fixed, **assignment}
        for i in range(4):
            row_values = [full_assignment.get((i, j)) for j in range(4)]
            if not all_different(row_values):
                return False
        return True
    
    def col_constraint(assignment):
        """All values in column must be different"""
        full_assignment = {**fixed, **assignment}
        for j in range(4):
            col_values = [full_assignment.get((i, j)) for i in range(4)]
            if not all_different(col_values):
                return False
        return True
    
    def box_constraint(assignment):
        """All values in 2x2 box must be different"""
        full_assignment = {**fixed, **assignment}
        for box_i in range(0, 4, 2):
            for box_j in range(0, 4, 2):
                box_values = [full_assignment.get((i, j)) 
                             for i in range(box_i, box_i + 2)
                             for j in range(box_j, box_j + 2)]
                if not all_different(box_values):
                    return False
        return True
    
    constraints = [row_constraint, col_constraint, box_constraint]
    
    csp = CSP(variables, domains, constraints)
    
    start = time.time()
    solution = csp.solve()
    elapsed = time.time() - start
    
    if solution:
        # Merge with fixed values
        full_solution = {**fixed, **solution}
        print("\nSolved in {:.3f}ms:".format(elapsed * 1000))
        for i in range(4):
            row = [full_solution[(i, j)] for j in range(4)]
            print(' '.join(map(str, row)))
        return True
    else:
        print("\nNo solution found")
        return False

def solve_graph_coloring():
    """Map coloring problem"""
    print("\n" + "="*70)
    print("CSP SOLVER: GRAPH 3-COLORING")
    print("="*70)
    
    # Graph: Australia map (simplified)
    regions = ['WA', 'NT', 'SA', 'Q', 'NSW', 'V']
    neighbors = {
        'WA': ['NT', 'SA'],
        'NT': ['WA', 'SA', 'Q'],
        'SA': ['WA', 'NT', 'Q', 'NSW', 'V'],
        'Q': ['NT', 'SA', 'NSW'],
        'NSW': ['Q', 'SA', 'V'],
        'V': ['SA', 'NSW']
    }
    
    colors = ['red', 'green', 'blue']
    domains = {region: colors.copy() for region in regions}
    
    def neighbor_constraint(assignment):
        """Adjacent regions must have different colors"""
        for region, color in assignment.items():
            for neighbor in neighbors[region]:
                if neighbor in assignment and assignment[neighbor] == color:
                    return False
        return True
    
    csp = CSP(regions, domains, [neighbor_constraint])
    
    start = time.time()
    solution = csp.solve()
    elapsed = time.time() - start
    
    if solution:
        print(f"\nSolved in {elapsed*1000:.3f}ms:")
        for region, color in sorted(solution.items()):
            print(f"  {region}: {color}")
        return True
    else:
        print("\nNo solution found")
        return False

if __name__ == "__main__":
    print("\n" + "="*70)
    print("CONSTRAINT SATISFACTION PROBLEM (CSP) SOLVER")
    print("="*70)
    
    sudoku_solved = solve_sudoku_example()
    coloring_solved = solve_graph_coloring()
    
    print("\n" + "="*70)
    print("CSP SOLVER RESULTS")
    print("="*70)
    print(f"✅ 4x4 Sudoku: {'Solved' if sudoku_solved else 'Failed'}")
    print(f"✅ Graph 3-coloring: {'Solved' if coloring_solved else 'Failed'}")
    
    print("\n✅ CSP solver implementation complete!")
    print("   Used in: Scheduling, planning, configuration problems")