Untitled

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""")