Program 8: Use constraint propagation to solve a Magic Square puzzle.

def solve_magic_square(n):
    """
    Solve nxn magic square using constraint propagation.
    Magic constant = n(n^2+1)/2
    """
    magic_sum = n * (n * n + 1) // 2
    square = [[0] * n for _ in range(n)]
    used = set()
    
    def is_valid(row, col, num):
        # Check if number already used
        if num in used:
            return False
        
        # Check row sum constraint
        row_sum = sum(square[row]) + num
        if row_sum > magic_sum:
            return False
        
        # Check column sum constraint
        col_sum = sum(square[i][col] for i in range(n)) + num
        if col_sum > magic_sum:
            return False
        
        return True
    
    def backtrack(pos):
        if pos == n * n:
            # Check all constraints
            for i in range(n):
                if sum(square[i]) != magic_sum:
                    return False
            for j in range(n):
                if sum(square[i][j] for i in range(n)) != magic_sum:
                    return False
            return True
        
        row, col = pos // n, pos % n
        
        for num in range(1, n * n + 1):
            if is_valid(row, col, num):
                square[row][col] = num
                used.add(num)
                
                if backtrack(pos + 1):
                    return True
                
                square[row][col] = 0
                used.remove(num)
        
        return False
    
    if backtrack(0):
        return square
    return None

print("Magic Square (3x3):")
magic = solve_magic_square(3)
if magic:
    for row in magic:
        print(f"  {row}")
print()

def solve_magic_square(n):
    """
    Solve nxn magic square using constraint propagation.
    Magic constant = n(n^2+1)/2
    """
    magic_sum = n * (n * n + 1) // 2
    square = [[0] * n for _ in range(n)]
    used = set()
    
    def is_valid(row, col, num):
        # Check if number already used
        if num in used:
            return False
        
        # Check row sum constraint
        row_sum = sum(square[row]) + num
        if row_sum > magic_sum:
            return False
        
        # Check column sum constraint
        col_sum = sum(square[i][col] for i in range(n)) + num
        if col_sum > magic_sum:
            return False
        
        return True
    
    def backtrack(pos):
        if pos == n * n:
            # Check all constraints
            for i in range(n):
                if sum(square[i]) != magic_sum:
                    return False
            for j in range(n):
                if sum(square[i][j] for i in range(n)) != magic_sum:
                    return False
            return True
        
        row, col = pos // n, pos % n
        
        for num in range(1, n * n + 1):
            if is_valid(row, col, num):
                square[row][col] = num
                used.add(num)
                
                if backtrack(pos + 1):
                    return True
                
                square[row][col] = 0
                used.remove(num)
        
        return False
    
    if backtrack(0):
        return square
    return None

print("Magic Square (3x3):")
magic = solve_magic_square(3)
if magic:
    for row in magic:
        print(f"  {row}")
print()