# Untitled

unknown
python
3 years ago
1.8 kB
2
Indexable
Never
```from random import shuffle
from math import sqrt
import sys

class SudokuState:
def __init__(self, size, field):
self.size = size
self.sqrt_size = int(sqrt(size))
self.size2 = size * size
self.square = field
self.base = list(range(10))

def free_nums(self, i, j) -> list:
free = [1] * 10
free[0] = 0
sq_i = (i // self.sqrt_size) * self.sqrt_size
sq_j = (j // self.sqrt_size) * self.sqrt_size

for k in range(9):
qi = k // self.sqrt_size
qj = k % self.sqrt_size
free[self.square[i][k]] = 0
free[self.square[k][j]] = 0
free[self.square[sq_i + qi][sq_j + qj]] = 0

return free

def paste_num(state: SudokuState, k: int) -> bool:
if k == state.size2:
return True
i: int = k // state.size
j: int = k % state.size
if state.square[i][j] != 0:
return paste_num(state, k + 1)

free = state.free_nums(i, j)
shuffle(state.base)

for val in state.base:
if not free[val]:
continue
state.square[i][j] = val
if paste_num(state, k + 1):
return True

state.square[i][j] = 0
return False

def pretty_print(m):
print('\n'.join(map(''.join, [map(str, r) for r in m])))

def main(data):
field = [list(map(int, r)) for r in data.split()]
sudoku = SudokuState(9, field)
paste_num(sudoku, 0)
pretty_print(sudoku.square)

if __name__ == '__main__':
main("""800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400""")
```