python thing

thing.py

import numpy as np
import math
import random
import time

def gcd_of_list(lst):
    """Returns GCD of a list of numbers, ignoring zeros."""
    filtered_lst = [num for num in lst if num != 0]  # Ignore zeros
    if not filtered_lst:
        return 0  # If all are zeros, return 0
    result = filtered_lst[0]
    for num in filtered_lst[1:]:
        result = math.gcd(result, num)
        if result == 1:  # No need to continue if GCD is already 1
            return 1
    return result

def is_valid_number(grid, row, col, num):
    """Check if 'num' can be placed at grid[row, col] without breaking uniqueness."""
    # Check row and column uniqueness
    if num in grid[row, :] or num in grid[:, col]:
        return False

    # Check 3×3 square uniqueness
    start_x, start_y = (row // 3) * 3, (col // 3) * 3
    if num in grid[start_x:start_x+3, start_y:start_y+3]:
        return False

    return True

def fill_grid(grid, predefined):
    """Fills the grid while keeping predefined numbers unchanged."""
    empty_cells = [(r, c) for r in range(9) for c in range(9) if (r, c) not in predefined]
    random.shuffle(empty_cells)  # Shuffle for randomness

    def backtrack(index):
        """Recursive backtracking function to fill the grid."""
        if index == len(empty_cells):
            return True  # All cells are filled

        row, col = empty_cells[index]
        for num in range(1, 10):  # Try numbers 1-9
            if is_valid_number(grid, row, col, num):
                grid[row, col] = num
                if backtrack(index + 1):
                    return True
                grid[row, col] = 0  # Reset on failure

        return False  # No valid number found

    return backtrack(0)  # Start backtracking

def generate_grid():
    """Generates a 9x9 grid while keeping predefined values fixed."""
    grid = np.zeros((9, 9), dtype=int)

    # Step 1: Predefined numbers (1-based indexing given, convert to 0-based)
    predefined = {
        (0, 7): 2,  # Row 1, Column 8
        (1, 8): 5,  # Row 2, Column 9
        (2, 1): 2,  # Row 3, Column 2
        (3, 2): 0,  # Row 4, Column 3
        # Row 5 is empty
        (5, 3): 2,  # Row 6, Column 4
        (6, 4): 0,  # Row 7, Column 5
        (7, 5): 2,  # Row 8, Column 6
        (8, 6): 5   # Row 9, Column 7
    }

    # Place predefined values
    for (r, c), val in predefined.items():
        grid[r, c] = val

    # Step 2: Fill remaining numbers with a valid Sudoku-like solution
    if not fill_grid(grid, predefined):
        raise Exception("Failed to generate a valid grid.")

    # Step 3: Ensure row GCD is greater than 3x3 square GCD
    for row in range(9):
        square_x, square_y = (row // 3) * 3, (row % 3) * 3
        square_numbers = [grid[i, j] for i in range(square_x, square_x+3) for j in range(square_y, square_y+3)]
        square_gcd = gcd_of_list(square_numbers)

        row_numbers = list(grid[row, :])
        row_gcd = gcd_of_list(row_numbers)

        if row_gcd <= square_gcd:
            # Adjust row by swapping values (excluding predefined ones)
            for i in range(9):
                if (row, i) not in predefined:
                    new_val = random.randint(1, 9)
                    while new_val in grid[row, :] or new_val in grid[:, i]:  # Ensure uniqueness
                        new_val = random.randint(1, 9)
                    grid[row, i] = new_val

    return grid

# Measure Execution Time
start_time = time.time()
grid = generate_grid()
end_time = time.time()

print(grid)
print(f"Execution Time: {end_time - start_time:.4f} seconds")