Original seed Sudoku solver used in GEPA optimization

sudoku_solver_seed.py

import numpy as np
from collections import defaultdict

def get_cell_bounds(idx): 
    x, y = idx; return ((x//3)*3, (x//3)*3+3), ((y//3)*3, (y//3)*3+3)

def get_used_numbers(grid, idx):
    x, y = idx; row, col = grid[x, :], grid[:, y]
    (x1,x2), (y1,y2) = get_cell_bounds(idx); box = grid[x1:x2, y1:y2].flatten()
    return np.unique(np.concatenate([row, col, box])[np.concatenate([row, col, box]) != 0])

def get_possible(grid, idx): 
    used = set(get_used_numbers(grid, idx))
    return np.array([n for n in range(1,10) if n not in used])

def init_possibilities(grid):
    empty_cells = np.argwhere(grid == 0)
    return {tuple(int(x) for x in c): get_possible(grid, c) for c in empty_cells}

def find_naked_singles(possibilities): return [(idx, int(val[0])) for idx, val in possibilities.items() if len(val) == 1]

def find_hidden_single(possibilities, idx, filter_func):
    number_counts = {}
    for pos, vals in possibilities.items():
        if filter_func(pos, idx):
            for val in vals: 
                if val in number_counts: number_counts[val] = None
                else: number_counts[val] = pos
    for number, pos in number_counts.items():
        if pos is not None: return pos, int(number)

def find_hidden_single_grid(possibilities, grid_coordinate):
    inverted_map = defaultdict(list)
    grid_c_x, grid_c_y = grid_coordinate
    grid_x, grid_y = (3*grid_c_x, 3*grid_c_x + 3), (3*grid_c_y, 3*grid_c_y + 3)
    for pos, vals in possibilities.items():
        x, y = pos
        if (grid_x[0] <= x < grid_x[1] and grid_y[0] <= y < grid_y[1]):
            for val in vals: inverted_map[int(val)].append(pos)
    for number, cells in inverted_map.items():
        if len(cells) == 1: return cells[0], number

def find_hidden_singles(poss): 
    grids = [(x,y) for x in range(3) for y in range(3)]
    for i in range(9):
        if hs := find_hidden_single(poss, i, lambda pos, idx: pos[0] == idx): return [hs]
        if hs := find_hidden_single(poss, i, lambda pos, idx: pos[1] == idx): return [hs]
    for grid in grids: 
        if hs := find_hidden_single_grid(poss, grid): return [hs]
    return []

def update_possibilities(grid, possibilities, idx, val):
    x, y = idx; (x1,x2), (y1,y2) = get_cell_bounds(idx)
    return {pos: vals[vals != val] if (pos[0] == x or pos[1] == y or (x1 <= pos[0] < x2 and y1 <= pos[1] < y2)) else vals 
            for pos, vals in possibilities.items() if pos != idx}

def solve_step(grid, possibilities):
    new_grid, new_poss = grid.copy(), possibilities
    singles = find_naked_singles(possibilities)
    if singles: 
        idx, val = singles[0]
        new_grid[idx] = val
        new_poss = update_possibilities(new_grid, new_poss, idx, val)
        return new_grid, new_poss
    if hs := find_hidden_singles(possibilities):
        idx, val = hs[0]
        new_grid[idx] = val
        new_poss = update_possibilities(new_grid, new_poss, idx, val)
    return new_grid, new_poss

def check_contradictions(poss): return bool([1 for x in poss.values() if len(x) == 0])

def is_valid_sudoku(grid):
    for i in range(9):
        row = grid[i, :][grid[i, :] != 0]
        col = grid[:, i][grid[:, i] != 0]
        if len(row) != len(np.unique(row)) or len(col) != len(np.unique(col)): return False
        box_r, box_c = (i//3)*3, (i%3)*3
        box = grid[box_r:box_r+3, box_c:box_c+3].flatten()
        box = box[box != 0]
        if len(box) != len(np.unique(box)): return False
    return True

def solve_backtrack(grid):
    current_grid, current_poss = grid.copy(), init_possibilities(grid)
    while find_naked_singles(current_poss) or find_hidden_singles(current_poss): 
        current_grid, current_poss = solve_step(current_grid, current_poss)
    if not current_poss: return current_grid
    if check_contradictions(current_poss): return None
    idx, values = min(current_poss.items(), key=lambda x: len(x[1]))
    for val in values:
        new_grid = current_grid.copy()
        new_grid[idx] = val
        result = solve_backtrack(new_grid)
        if result is not None: return result
    return None

def puzzle_to_grid(puzzle_str):
    return np.array([int(c) if c != '.' else 0 for c in puzzle_str]).reshape(9, 9)

def grid_to_string(grid):
    return ''.join(str(x) for x in grid.flatten())

def solve(puzzle_str):
    return grid_to_string(solve_backtrack(puzzle_to_grid(puzzle_str)))