| """
|
| Валидатор судоку для проверки корректности
|
| """
|
| 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
|
|
|
|
|
| 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 |
