File size: 4,460 Bytes
9bb24f8 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | """
Валидатор судоку для проверки корректности
"""
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 |