"""
Валидатор судоку для проверки корректности
"""
import numpy as np
from typing import List, Tuple, Optional

class SudokuValidator:
    """Класс для проверки корректности судоку"""
    
    def __init__(self):
        self.size = 9
        self.box_size = 3
    
    def is_valid_puzzle(self, grid: np.ndarray) -> bool:
        """
        Проверяет, что пазл корректен (нет конфликтов)
        """
        if grid.shape != (9, 9):
            return False
        
        # Проверка значений
        if not np.all((grid >= 0) & (grid <= 9)):
            return False
        
        # Проверка строк
        for i in range(9):
            if not self._is_valid_line(grid[i, :]):
                return False
        
        # Проверка столбцов
        for j in range(9):
            if not self._is_valid_line(grid[:, j]):
                return False
        
        # Проверка блоков 3x3
        for box_i in range(3):
            for box_j in range(3):
                box = grid[
                    box_i*3:(box_i+1)*3,
                    box_j*3:(box_j+1)*3
                ].flatten()
                if not self._is_valid_line(box):
                    return False
        
        return True
    
    def _is_valid_line(self, line: np.ndarray) -> bool:
        """Проверка строки/столбца/блока на дубликаты"""
        non_zero = line[line != 0]
        return len(non_zero) == len(set(non_zero))
    
    def is_valid_placement(self, grid: np.ndarray, row: int, col: int) -> bool:
        """Проверка конкретной клетки"""
        if grid[row, col] == 0:
            return True
        
        val = grid[row, col]
        grid[row, col] = 0
        
        # Проверка строки
        if val in grid[row, :]:
            grid[row, col] = val
            return False
        
        # Проверка столбца
        if val in grid[:, col]:
            grid[row, col] = val
            return False
        
        # Проверка блока
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        box = grid[box_row:box_row+3, box_col:box_col+3]
        if val in box:
            grid[row, col] = val
            return False
        
        grid[row, col] = val
        return True
    
    def has_unique_solution(self, grid: np.ndarray) -> bool:
        """
        Проверка на уникальность решения
        Использует backtracking для поиска решений
        """
        solutions = []
        self._solve_with_limit(grid.copy(), solutions, limit=2)
        return len(solutions) == 1
    
    def _solve_with_limit(self, grid: np.ndarray, solutions: list, limit: int):
        """Поиск решений с ограничением"""
        if len(solutions) >= limit:
            return
        
        empty = self._find_empty(grid)
        if not empty:
            solutions.append(grid.copy())
            return
        
        row, col = empty
        
        for num in range(1, 10):
            if self._is_safe(grid, row, col, num):
                grid[row, col] = num
                self._solve_with_limit(grid, solutions, limit)
                grid[row, col] = 0
    
    def _find_empty(self, grid: np.ndarray) -> Optional[Tuple[int, int]]:
        """Находит пустую клетку"""
        for i in range(9):
            for j in range(9):
                if grid[i, j] == 0:
                    return (i, j)
        return None
    
    def _is_safe(self, grid: np.ndarray, row: int, col: int, num: int) -> bool:
        """Проверка безопасности установки числа"""
        # Проверка строки
        if num in grid[row, :]:
            return False
        
        # Проверка столбца
        if num in grid[:, col]:
            return False
        
        # Проверка блока
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        box = grid[box_row:box_row+3, box_col:box_col+3]
        if num in box:
            return False
        
        return True