Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import copy
- import sys
- import random
- import itertools
- global_flag = True
- def get_column(col_in, mat):
- res = []
- for i in range(9):
- if mat[i][col_in] != 0:
- res.append(mat[i][col_in])
- return res
- def get_row(row_id, mat):
- res = []
- for i in range(9):
- if mat[row_id][i] != 0:
- res.append(mat[row_id][i])
- return res
- def get_cell(row_id, col_id, mat):
- res = []
- nach_x = row_id // 3 * 3
- nach_y = col_id // 3 * 3
- if mat[nach_x][nach_y] != 0:
- res.append(mat[nach_x][nach_y])
- if mat[nach_x][nach_y + 1] != 0:
- res.append(mat[nach_x][nach_y + 1])
- if mat[nach_x][nach_y + 2] != 0:
- res.append(mat[nach_x][nach_y + 2])
- if mat[nach_x + 1][nach_y] != 0:
- res.append(mat[nach_x + 1][nach_y])
- if mat[nach_x + 1][nach_y + 1] != 0:
- res.append(mat[nach_x + 1][nach_y + 1])
- if mat[nach_x + 1][nach_y + 2] != 0:
- res.append(mat[nach_x + 1][nach_y + 2])
- if mat[nach_x + 2][nach_y] != 0:
- res.append(mat[nach_x + 2][nach_y])
- if mat[nach_x + 2][nach_y + 1] != 0:
- res.append(mat[nach_x + 2][nach_y + 1])
- if mat[nach_x + 2][nach_y + 2] != 0:
- res.append(mat[nach_x + 2][nach_y + 2])
- return res
- def possible_val(mat, row_id, col_id):
- col = get_column(col_id, mat)
- r = get_row(row_id, mat)
- c = get_cell(row_id, col_id, mat)
- all_v = col + r + c
- res = {1, 2, 3, 4, 5, 6, 7, 8, 9}.difference(set(all_v))
- return res
- def solve(mat):
- global global_flag
- if global_flag:
- flag = True
- flag2 = False
- while flag:
- flag = False
- for i in range(9):
- for j in range(9):
- if mat[i][j] != 0:
- continue
- else:
- pos_val = possible_val(mat, i, j)
- if len(pos_val) == 0:
- flag2 = True
- if len(pos_val) == 1:
- flag = True
- mat[i][j] = pos_val.pop()
- if flag2:
- break
- if not flag2:
- min_possible_len = 9
- series = None
- for i in range(9):
- for j in range(9):
- if mat[i][j] != 0:
- continue
- else:
- pos_val = possible_val(mat, i, j)
- if len(pos_val) < min_possible_len:
- min_possible_len = len(pos_val)
- series = ((i, j), pos_val)
- if series is None:
- print_mat(mat)
- global_flag = False
- return True
- else:
- for el in series[1]:
- solution = copy.deepcopy(mat)
- solution[series[0][0]][series[0][1]] = el
- solve(solution)
- def print_mat(mat):
- for row in mat:
- for el in row:
- print(el, end='')
- print()
- def fill_random(mat):
- for i in range(9):
- new_cell = find_zero(mat)
- val = new_cell[1][random.randint(0, len(new_cell[1]) - 1)]
- mat[new_cell[0][0]][new_cell[0][1]] = val
- def read_mat():
- all_rows = sys.stdin.read().split('\n')
- res_mat = []
- for el in all_rows:
- row = []
- for sub_el in el:
- if sub_el != ' ':
- row.append(int(sub_el))
- res_mat.append(row)
- return res_mat
- def find_zero(mat):
- flag = False
- for i in range(9):
- if flag:
- break
- for j in range(9):
- if mat[i][j] == 0:
- pos_val = list(possible_val(mat, i, j))
- if len(pos_val) > 0:
- return ((i, j), pos_val)
- def start_prog():
- mat = read_mat()
- fill_random(mat)
- solve(mat)
- start_prog()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement