import random
grid=[[5,3,.,.,7,.,.,.,.],
[6,.,.,1,9,5,.,.,.],
[.,9,8,.,.,.,.,6,.],
[8,.,.,.,6,.,.,.,3],
[4,.,.,8,.,3,.,.,1],
[7,.,.,.,2,.,.,.,6],
[.,6,.,.,.,.,2,8,.],
[.,.,.,4,1,9,.,.,5],
[.,.,.,.,8,.,.,7,9]]
def find_empty_position(grid):
    for r in range(9):
        for w in range(9):
            if grid[r][w] == .:
                return (r, w)
def get_row(values, pos):
    for i in range(9):
        if i==pos[0]:
            return values[i]
def get_col(values, pos):
    r, w = pos
    return [values[r][w] for i in range(9)]
def get_block(values, pos):
    pos=r,w
    a = 3 * (r%3)
    b =3 * (w%3)
    return [values[a+r][b+w] for r in range(3) for w in range(3)]
def find_possible_values(grid, pos):
    check_col=get_col(grid,pos)
    check_row=get_row(grid,pos)
    check_block=get_block(grid,pos)
    n=random.randint(1,9)
    if n not in check_block:
        if n not in check_row:
            if n not in check_col:
                return n
def solve(grid):
    pos=find_empty_position(grid)
    if not pos:
        return grid
    r,w=pos
    for n in find_possible_values(grid, pos):
	    grid[r][w] = n
        if solve(grid):
		    s=solve(grid)
            return s
		else:
		    grid[r][w] = .
    if not pos:
        return grid

 import random
grid=[[5,3,'.','.',7,'.','.','.','.'],
[6,'.','.',1,9,5,'.','.','.'],
['.',9,8,'.','.','.','.',6,'.'],
[8,'.','.','.',6,'.','.','.',3],
[4,'.','.',8,'.',3,'.','.',1],
[7,'.','.','.',2,'.','.','.',6],
['.',6,'.','.','.','.',2,8,'.'],
['.','.','.',4,1,9,'.','.',5],
['.','.','.','.',8,'.','.',7,9]]
def find_empty_position(grid):
    for r in range(9):
        for w in range(9):
            if grid[r][w] == '.':
                return (r, w)
def get_row(values, pos):
    for i in range(9):
        if i==pos[0]:
            return values[i]
def get_col(values, pos):
    r, w = pos
    return [values[r][w] for i in range(9)]
def get_block(values, pos):
    r,w=pos
    a = 3 * (r%3)
    b =3 * (w%3)
    return [values[a+r][b+w] for r in range(3) for w in range(3)]
def find_possible_values(grid, pos):
        r,w=pos
        row = get_row(grid, pos)
        column = get_col(grid, pos)
        block = get_block(grid, pos)
        options = list(range(1, 10))
        random.shuffle(options)
        for i in options:
            if (i not in row  and i not in col and i not in block):
                 grid[r][w]=i
                 return grid[r][w]                    #возвращает список чисел,которых нет в колонке,в блоке,в строчке
                    
def solve(grid):
    pos=find_empty_position(grid)
    if not pos:
        return grid
    r,w=pos
    for n in  find_possible_values(grid, pos):
        grid[r][w]=n
    s=solve(grid)
    if s:
        return s
    else:
        grid[r][w] = '.'
        
print(solve(grid))

 def find_possible_values(grid, pos):
        r,w=pos
        row = get_row(grid, pos)
        print('row:',row)
        column = get_col(grid, pos)
        print('column:',column)
        block = get_block(grid, pos)
        print('block:',block)
        options = list(range(1, 10))
        random.shuffle(options)
        for i in options:
            if (i not in row  and i not in column and i not in block):
                 grid[r][w]=i
                 print('G',grid[r][w])
                 return grid[r][w]  

 def get_col(values,pos):
    f,w=pos
    return [values[r][w] for r in range(len(values))]

 def find_possible_values(grid, pos):
    r,w=pos
    row = get_row(grid, pos)
    column = get_col(grid, pos)
    block = get_block(grid, pos)
    options = list(range(1, 10))
    random.shuffle(options)
    return [i for i in options if (i not in row  and i not in column and i not in block)]

def solve(grid):
    pos=find_empty_position(grid) # ищем пустую ячейку
    if not pos:                              # если не нашли:
        return grid                         # вернуть заполненый грид, завершить процедуру
    r,w=pos                                 #  присваиваем r,w - координаты пустой ячейки 
    for n in  find_possible_values(grid, pos):  # ищем возможные варианты 
        grid[r][w]=n                                         #  и в цикле присваиваем пустой ячейке возможные 
                                                                   # значения, пока не дойдем до последнего
    s=solve(grid)                          # вызываем рекурсивно себяже
    if s:                                        # если вызванная  функция чтото вернула                  
        return s                               # возвращаем то что она вернула
    else:                                       # иначе оставляем ячейку пустой, функция вернет None
        grid[r][w] = '.'