gistfile1.txt

from constraint import Problem, AllDifferentConstraint
import time
import itertools

def create_sudoku_csp(initial_grid):
    problem = Problem()
    
    # Define variables and their domains
    # Each cell is represented by a tuple (row, col)
    for i, j in itertools.product(range(9), range(9)):
        if initial_grid[i][j] == 0:
            problem.addVariable((i, j), range(1, 10))
        else:
            problem.addVariable((i, j), [initial_grid[i][j]])
    
    # Add row constraints
    for row in range(9):
        problem.addConstraint(
            AllDifferentConstraint(),
            [(row, col) for col in range(9)]
        )
    
    # Add column constraints
    for col in range(9):
        problem.addConstraint(
            AllDifferentConstraint(),
            [(row, col) for row in range(9)]
        )
    
    # Add 3x3 box constraints
    for box_row, box_col in itertools.product(range(0, 9, 3), range(0, 9, 3)):
        box_variables = [
            (row, col)
            for row in range(box_row, box_row + 3)
            for col in range(box_col, box_col + 3)
        ]
        problem.addConstraint(AllDifferentConstraint(), box_variables)
    
    return problem

def print_grid(grid):
    """Print the Sudoku grid in a nice format."""
    horizontal_line = "+" + "-" * 7 + "+" + "-" * 7 + "+" + "-" * 7 + "+"
    print(horizontal_line)
    for i in range(9):
        if i > 0 and i % 3 == 0:
            print(horizontal_line)
        row_str = "|"
        for j in range(9):
            if j > 0 and j % 3 == 0:
                row_str += "|"
            row_str += f" {grid[i][j]}"
        row_str += " |"
        print(row_str)
    print(horizontal_line)

def solution_to_grid(solution):
    """Convert the CSP solution dictionary to a 9x9 grid."""
    grid = [[0] * 9 for _ in range(9)]
    for (row, col), value in solution.items():
        grid[row][col] = value
    return grid

def solve_sudoku(initial_grid):
    """Solve the Sudoku puzzle and return the solution."""
    print("Original puzzle:")
    print_grid(initial_grid)
    
    start_time = time.time()
    
    # Create and solve the CSP
    problem = create_sudoku_csp(initial_grid)
    solution = problem.getSolution()
    
    end_time = time.time()
    
    if solution:
        print("\nSolution found!")
        solution_grid = solution_to_grid(solution)
        print_grid(solution_grid)
        print(f"\nTime taken: {end_time - start_time:.4f} seconds")
        return solution_grid
    else:
        print("\nNo solution exists!")
        return None

# Example usage
if __name__ == "__main__":
    # Example puzzle (0 represents empty cells)
    puzzle = [
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9]
    ]
    
    solution = solve_sudoku(puzzle)