■

1. import sys
   sys.setrecursionlimit(10**7)
   
   input_grid = [[0, 0, 8, 7, 0, 0, 0, 1, 0],
   [0, 5, 0, 0, 0, 3, 0, 0, 0],
   [0, 0, 0, 2, 4, 8, 0, 0, 0],
   [0, 9, 0, 0, 0, 0, 0, 2, 4],
   [0, 3, 6, 0, 0, 0, 0, 0, 1],
   [4, 0, 0, 0, 0, 0, 5, 0, 0],
   [0, 0, 0, 3, 8, 7, 0, 0, 0],
   [0, 0, 0, 9, 0, 0, 0, 0, 2],
   [0, 0, 7, 0, 0, 6, 0, 5, 0]]
   
   def find_next_cell(grid):
   for y in range(9):
   for x in range(9):
   if grid[y][x] == 0:
   # 埋まっていない座標を返す
   return y, x
   # すべてのマスに数字が入っている状態
   return -1, -1
   
   # 条件を満たすかの判定
   def is_valid(grid, y, x, value):
   # 横のチェック
   is_row = value not in grid[y]
   # 縦のチェック
   is_column = value not in [i[x] for i in grid]
   # ブロックを取り出す
   blk_x, blk_y = (x//3) * 3, (y//3) * 3
   blk_grid = [i[blk_x:blk_x + 3] for i in input_grid[blk_y:blk_y + 3]]
   # ブロックのチェック
   is_block = value not in sum(blk_grid, )
   # 有効チェック
   return all([is_row, is_column, is_block])
   
   # すべてのマスを調べて数字が最大で何個入りそうなのかを確認する
   def possibility(grid, y, x):
   # インデックス番号
   idx = 0
   # 今考えているマスにどれだけの数字が入りそうなのか
   mass2 =
   # 今考えているマスに
   number2 =
   tmp =
   if grid[y][x] != 0:
   return True
   else:
   cnt = 0
   for value in range(1, 10):
   # もし今考えている数字が入りそうなら
   if is_valid(grid, y, x, value):
   # 最大で入る可能性数を足す
   cnt += 1
   tmp.append(value)
   # そのマスには cnt の数だけ入りそう
   mass2.append([cnt, y, x])
   number2.append(tmp)
   return *mass2, *number2
   
   mass=
   number=
   mass_num=[]
   for i in range(9):
   for j in range(9):
   if possibility(input_grid, j, i) != True:
   mass.append(possibility(input_grid, j, i)[0])
   number.append(possibility(input_grid, j, i)[1])
   for i in range(len(mass)):
   mass_num.append([mass[i], number[i]])
   mass_num.sort()
   y = mass_num[0][0][1]
   x = mass_num[0][0][2]
   idx = 0
   #print(mass_num[0][0][3]) インデックス番号は 0 0 3 だ！()
   
   # 実際に数字を再帰的に入れてみる
   def solve_sudoku(grid, idx):
   #[print(i) for i in input_grid]
   Y, X = find_next_cell(grid)
   if Y == X == -1:
   return True
   for value in mass_num[idx][1]:
   if is_valid(grid, mass_num[idx][0][1], mass_num[idx][0][2], value):
   grid[mass_num[idx][0][1]][mass_num[idx][0][2]] = value
   # 次へ
   idx += 1
   if solve_sudoku(grid, idx):
   return True
   grid[mass_num[idx][0][1]][mass_num[idx][0][2]] = 0
   idx -= 1
   return False
   
   print(solve_sudoku(input_grid, idx))
   [print(i) for i in input_grid]
2.  
3.