Advertisement
Guest User

Untitled

a guest
Feb 27th, 2020
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.95 KB | None | 0 0
  1. import copy
  2. import sys
  3. import random
  4. import itertools
  5.  
  6. global_flag = True
  7.  
  8.  
  9. def get_column(col_in, mat):
  10.     res = []
  11.     for i in range(9):
  12.         if mat[i][col_in] != 0:
  13.             res.append(mat[i][col_in])
  14.     return res
  15.  
  16.  
  17. def get_row(row_id, mat):
  18.     res = []
  19.     for i in range(9):
  20.         if mat[row_id][i] != 0:
  21.             res.append(mat[row_id][i])
  22.     return res
  23.  
  24.  
  25. def get_cell(row_id, col_id, mat):
  26.     res = []
  27.     nach_x = row_id // 3 * 3
  28.     nach_y = col_id // 3 * 3
  29.     if mat[nach_x][nach_y] != 0:
  30.         res.append(mat[nach_x][nach_y])
  31.     if mat[nach_x][nach_y + 1] != 0:
  32.         res.append(mat[nach_x][nach_y + 1])
  33.     if mat[nach_x][nach_y + 2] != 0:
  34.         res.append(mat[nach_x][nach_y + 2])
  35.     if mat[nach_x + 1][nach_y] != 0:
  36.         res.append(mat[nach_x + 1][nach_y])
  37.     if mat[nach_x + 1][nach_y + 1] != 0:
  38.         res.append(mat[nach_x + 1][nach_y + 1])
  39.     if mat[nach_x + 1][nach_y + 2] != 0:
  40.         res.append(mat[nach_x + 1][nach_y + 2])
  41.     if mat[nach_x + 2][nach_y] != 0:
  42.         res.append(mat[nach_x + 2][nach_y])
  43.     if mat[nach_x + 2][nach_y + 1] != 0:
  44.         res.append(mat[nach_x + 2][nach_y + 1])
  45.     if mat[nach_x + 2][nach_y + 2] != 0:
  46.         res.append(mat[nach_x + 2][nach_y + 2])
  47.     return res
  48.  
  49.  
  50. def possible_val(mat, row_id, col_id):
  51.     col = get_column(col_id, mat)
  52.     r = get_row(row_id, mat)
  53.     c = get_cell(row_id, col_id, mat)
  54.     all_v = col + r + c
  55.     res = {1, 2, 3, 4, 5, 6, 7, 8, 9}.difference(set(all_v))
  56.     return res
  57.  
  58.  
  59. def solve(mat):
  60.     global global_flag
  61.     if global_flag:
  62.         flag = True
  63.         flag2 = False
  64.         while flag:
  65.             flag = False
  66.             for i in range(9):
  67.                 for j in range(9):
  68.                     if mat[i][j] != 0:
  69.                         continue
  70.                     else:
  71.                         pos_val = possible_val(mat, i, j)
  72.                         if len(pos_val) == 0:
  73.                             flag2 = True
  74.                         if len(pos_val) == 1:
  75.                             flag = True
  76.                             mat[i][j] = pos_val.pop()
  77.             if flag2:
  78.                 break
  79.         if not flag2:
  80.             min_possible_len = 9
  81.             series = None
  82.             for i in range(9):
  83.                 for j in range(9):
  84.                     if mat[i][j] != 0:
  85.                         continue
  86.                     else:
  87.                         pos_val = possible_val(mat, i, j)
  88.                         if len(pos_val) < min_possible_len:
  89.                             min_possible_len = len(pos_val)
  90.                             series = ((i, j), pos_val)
  91.             if series is None:
  92.                 print_mat(mat)
  93.                 global_flag = False
  94.                 return True
  95.             else:
  96.                 for el in series[1]:
  97.                     solution = copy.deepcopy(mat)
  98.                     solution[series[0][0]][series[0][1]] = el
  99.                     solve(solution)
  100.  
  101.  
  102. def print_mat(mat):
  103.     for row in mat:
  104.         for el in row:
  105.             print(el, end='')
  106.         print()
  107.  
  108.  
  109. def fill_random(mat):
  110.     for i in range(9):
  111.         new_cell = find_zero(mat)
  112.         val = new_cell[1][random.randint(0, len(new_cell[1]) - 1)]
  113.         mat[new_cell[0][0]][new_cell[0][1]] = val
  114.  
  115.  
  116. def read_mat():
  117.     all_rows = sys.stdin.read().split('\n')
  118.     res_mat = []
  119.     for el in all_rows:
  120.         row = []
  121.         for sub_el in el:
  122.             if sub_el != ' ':
  123.                 row.append(int(sub_el))
  124.         res_mat.append(row)
  125.     return res_mat
  126.  
  127.  
  128. def find_zero(mat):
  129.     flag = False
  130.     for i in range(9):
  131.         if flag:
  132.             break
  133.         for j in range(9):
  134.             if mat[i][j] == 0:
  135.                 pos_val = list(possible_val(mat, i, j))
  136.                 if len(pos_val) > 0:
  137.                     return ((i, j), pos_val)
  138.  
  139.  
  140. def start_prog():
  141.     mat = read_mat()
  142.     fill_random(mat)
  143.     solve(mat)
  144.  
  145.  
  146. start_prog()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement