from collections import deque
from itertools import product

class CrossSumsCSP:
    def __init__(self, grid, rows, cols):
        self.grid = grid
        self.rows = rows
        self.cols = cols
        self.n_rows = len(grid)
        self.n_cols = len(grid[0])
        
        # Variables: chaque cellule (i,j) peut prendre la valeur 0 ou grid[i][j]
        self.variables = [(i, j) for i in range(self.n_rows) for j in range(self.n_cols)]
        
        # Domaines: {0, valeur_originale} pour chaque variable
        self.domains = {}
        for i in range(self.n_rows):
            for j in range(self.n_cols):
                self.domains[(i, j)] = {0, self.grid[i][j]}
        
        # Contraintes: une par ligne et une par colonne
        self.constraints = []
        
        # Contraintes de lignes
        for i in range(self.n_rows):
            variables_in_row = [(i, j) for j in range(self.n_cols)]
            self.constraints.append(('row', i, variables_in_row, self.rows[i]))
        
        # Contraintes de colonnes
        for j in range(self.n_cols):
            variables_in_col = [(i, j) for i in range(self.n_rows)]
            self.constraints.append(('col', j, variables_in_col, self.cols[j]))
        print(self.constraints)
    def is_consistent(self, assignment, constraint):
        """Vérifie si une assignation partielle est consistante avec une contrainte"""
        constraint_type, index, variables, target_sum = constraint
        
        current_sum = 0
        unassigned_count = 0
        max_possible = 0
        
        for var in variables:
            if var in assignment:
                current_sum += assignment[var]
            else:
                unassigned_count += 1
                # Contribution maximale possible de cette variable
                max_possible += max(self.domains[var])
        
        # Vérifier si c'est encore possible d'atteindre la somme cible
        if current_sum > target_sum:
            return False
        if current_sum + max_possible < target_sum:
            return False
        
        return True
    
    def revise(self, var1, var2, constraint):
        """Révise le domaine de var1 en fonction de var2 et de la contrainte"""
        revised = False
        constraint_type, index, variables, target_sum = constraint
        
        if var1 not in variables or var2 not in variables:
            return False
        
        to_remove = []
        
        for value1 in self.domains[var1]:
            # Vérifier si cette valeur pour var1 est compatible avec au moins une valeur de var2
            compatible = False
            
            for value2 in self.domains[var2]:
                # Créer une assignation partielle pour tester
                partial_assignment = {var1: value1, var2: value2}
                
                if self.is_consistent(partial_assignment, constraint):
                    compatible = True
                    break
            
            if not compatible:
                to_remove.append(value1)
        
        for value in to_remove:
            self.domains[var1].remove(value)
            revised = True
        
        return revised
    
    def get_related_constraints(self, var):
        """Retourne les contraintes qui impliquent cette variable"""
        related = []
        for constraint in self.constraints:
            if var in constraint[2]:  # constraint[2] sont les variables de la contrainte
                related.append(constraint)
        return related
    
    def ac3(self):
        """Algorithme AC-3 pour la consistance d'arc"""
        # Initialiser la queue avec tous les arcs
        queue = deque()
        
        for constraint in self.constraints:
            variables_in_constraint = constraint[2]
            # Ajouter tous les arcs entre les variables de cette contrainte
            for i in range(len(variables_in_constraint)):
                for j in range(i+1, len(variables_in_constraint)):
                    var1, var2 = variables_in_constraint[i], variables_in_constraint[j]
                    queue.append((var1, var2, constraint))
                    queue.append((var2, var1, constraint))
        
        while queue:
            var1, var2, constraint = queue.popleft()
            
            if self.revise(var1, var2, constraint):
                if len(self.domains[var1]) == 0:
                    return False  # Pas de solution
                
                # Ajouter les arcs affectés à la queue
                for other_constraint in self.get_related_constraints(var1):
                    if other_constraint != constraint:
                        for var in other_constraint[2]:
                            if var != var1 and var != var2:
                                queue.append((var, var1, other_constraint))
        
        return True
    
    def propagate_constraint(self, constraint):
        """Propage une contrainte spécifique pour réduire les domaines"""
        constraint_type, index, variables, target_sum = constraint
        
        # Calculer les valeurs min et max possibles
        min_sum = sum(min(self.domains[var]) for var in variables)
        max_sum = sum(max(self.domains[var]) for var in variables)
        
        # Si impossible, domaines vides
        if min_sum > target_sum or max_sum < target_sum:
            for var in variables:
                self.domains[var] = set()
            return False
        
        # Propagation plus fine
        for var in variables:
            to_remove = []
            for value in self.domains[var]:
                # Calculer la somme des autres variables
                other_min = sum(min(self.domains[other_var]) for other_var in variables if other_var != var)
                other_max = sum(max(self.domains[other_var]) for other_var in variables if other_var != var)
                
                # Vérifier si cette valeur peut mener à la somme cible
                if other_min + value > target_sum or other_max + value < target_sum:
                    to_remove.append(value)
            
            for value in to_remove:
                self.domains[var].remove(value)
        
        return True
    
    def constraint_propagation(self):
        """Applique la propagation de contraintes"""
        changed = True
        while changed:
            changed = False
            for constraint in self.constraints:
                if not self.propagate_constraint(constraint):
                    return False
                # Vérifier si des domaines ont été modifiés
                for var in self.variables:
                    if len(self.domains[var]) == 0:
                        return False
        return True
    
    def is_complete(self, assignment):
        """Vérifie si l'assignation est complète"""
        return len(assignment) == len(self.variables)
    
    def is_consistent_assignment(self, assignment):
        """Vérifie si l'assignation complète respecte toutes les contraintes"""
        for constraint in self.constraints:
            if not self.is_consistent(assignment, constraint):
                return False
        return True
    
    def select_unassigned_variable(self, assignment):
        """Sélectionne la prochaine variable à assigner (heuristique MRV)"""
        unassigned = [var for var in self.variables if var not in assignment]
        if not unassigned:
            return None
        
        # Heuristique MRV (Minimum Remaining Values)
        return min(unassigned, key=lambda var: len(self.domains[var]))
    
    def backtrack(self, assignment):
        """Recherche par backtracking avec propagation de contraintes"""
        if self.is_complete(assignment):
            return assignment
        
        var = self.select_unassigned_variable(assignment)
        if var is None:
            return None
        
        for value in sorted(self.domains[var]):
            assignment[var] = value
            
            # Sauvegarder les domaines avant la propagation
            saved_domains = {v: domain.copy() for v, domain in self.domains.items()}
            
            # Vérifier la consistance avec les contraintes
            consistent = True
            for constraint in self.get_related_constraints(var):
                if not self.is_consistent(assignment, constraint):
                    consistent = False
                    break
            
            if consistent:
                # Propager les contraintes
                if self.constraint_propagation():
                    result = self.backtrack(assignment)
                    if result is not None:
                        return result
            
            # Restaurer les domaines
            self.domains = saved_domains
            del assignment[var]
        
        return None
    
    def solve(self):
        """Résout le CSP en utilisant AC-3 et backtracking"""
        print("Application de AC-3...")
        
        # Appliquer AC-3 pour la consistance d'arc
        if not self.ac3():
            print("Aucune solution trouvée par AC-3")
            return None
        
        print("AC-3 terminé. Domaines après AC-3:")
        for var in self.variables:
            if len(self.domains[var]) > 1:
                print(f"Variable {var}: {self.domains[var]}")
        
        # Propagation de contraintes initiale
        if not self.constraint_propagation():
            print("Aucune solution trouvée après propagation")
            return None
        
        print("Démarrage du backtracking...")
        solution = self.backtrack({})
        
        if solution:
            # Convertir en grille
            result_grid = [[0 for _ in range(self.n_cols)] for _ in range(self.n_rows)]
            for (i, j), value in solution.items():
                result_grid[i][j] = value
            return result_grid
        
        return None

def solve_cross_sums_csp(grid, rows, cols):
    """Interface principale pour résoudre le problème Cross Sums avec CSP"""
    csp = CrossSumsCSP(grid, rows, cols)
    return csp.solve()

def print_solution(solution):
    """Affiche une solution de manière lisible"""
    if solution is None:
        print("Aucune solution trouvée")
        return
    
    for row in solution:
        print(row)

def verify_solution(solution, rows, cols):
    """Vérifie qu'une solution respecte les contraintes"""
    if solution is None:
        return False
    
    # Vérifier les lignes
    for i, row in enumerate(solution):
        if sum(row) != rows[i]:
            print(f"Erreur ligne {i}: somme = {sum(row)}, attendu = {rows[i]}")
            return False
    
    # Vérifier les colonnes
    for j in range(len(solution[0])):
        col_sum = sum(solution[i][j] for i in range(len(solution)))
        if col_sum != cols[j]:
            print(f"Erreur colonne {j}: somme = {col_sum}, attendu = {cols[j]}")
            return False
    
    return True

# Test avec l'exemple fourni

grid = [[3, 7, 2, 4], [4, 1, 6, 2], [1, 4, 8, 6], [3, 1, 6, 2]]
rows = [2, 3, 5, 8]
cols = [1, 5, 8, 4]

print("Grille originale:")
for row in grid:
    print(row)
print(f"\nContraintes - Lignes: {rows}, Colonnes: {cols}")

solution = solve_cross_sums_csp(grid, rows, cols)

print("\nSolution trouvée:")
print_solution(solution)

if verify_solution(solution, rows, cols):
    print("\n✓ Solution vérifiée avec succès!")
else:
    print("\n✗ Erreur dans la solution")