Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from typing import Tuple
- def generate_matrixes(start_matrix: list[list[int]], nulls_passed: int = 0) -> list[list[list[int]]]:
- if nulls_passed - 1 == count_nulls_in_matrix(start_matrix):
- return [start_matrix]
- coords = count_coords(start_matrix, nulls_passed)
- if coords is None:
- print("\n\n\n\n\n\n\nNI NI NI\n\n\n\n\n\n\n")
- x, y = coords
- numbers_we_can_put = get_possible_numbers(start_matrix, x, y)
- all_new_matrixes: list[list[list[int]]] = []
- for numb in numbers_we_can_put:
- new_matrix = my_deep_copy(start_matrix)
- new_matrix[x][y] = numb
- new_generated_matrixes = generate_matrixes(new_matrix, nulls_passed + 1)
- all_new_matrixes = my_extend(all_new_matrixes, new_generated_matrixes)
- return all_new_matrixes
- def my_extend(arr1: list[list[list]], arr2: list[list[list]]) -> list[list[list]]:
- for matrix in arr2:
- arr1.append(matrix)
- return arr1
- def my_deep_copy(arr: list[list]) -> list[list]:
- new_arr = []
- for i in range(len(arr)):
- new_row = []
- for j in range(len(arr[i])):
- new_row.append(arr[i][j])
- new_arr.append(new_row)
- return new_arr
- def count_coords(matrix: list[list[int]], at_null: int) -> Tuple[int, int]:
- numbers_passed = 0
- for ind1 in range(len(matrix)):
- for ind2 in range(len(matrix[ind1])):
- elem = matrix[ind1][ind2]
- if elem == 0 and numbers_passed != at_null:
- numbers_passed += 1
- elif elem == 0 and numbers_passed == at_null:
- return ind1, ind2
- def get_possible_numbers(matrix: list[int], i: int, j: int) -> list[int]:
- possible_numbers = get_canon_numbers()
- for ind_in_row in range(len(matrix[i])):
- elem_in_row = matrix[i][ind_in_row]
- if ind_in_row != j and elem_in_row != 0:
- try_to_remove(possible_numbers, elem_in_row)
- for ind_in_col in range(len(matrix)):
- elem_in_col = matrix[ind_in_col][j]
- if ind_in_col != i and elem_in_col != 0:
- try_to_remove(possible_numbers, elem_in_col)
- square = get_square(matrix, i, j)
- for ind_1 in range(3):
- for ind_2 in range(3):
- elem = square[ind_1][ind_2]
- if not(ind_1 == i and ind_2==j):
- if elem != 0:
- try_to_remove(possible_numbers, elem)
- return possible_numbers
- def try_to_remove(arr: list[int], numb: int) -> list:
- if numb in arr:
- arr.remove(numb)
- return arr
- def get_square(matrix: list[int], i: int, j: int) -> list[int]:
- square_i = i // 3
- square_j = j // 3
- square = []
- for ind_1 in range(3):
- square_row = []
- for ind_2 in range(3):
- elem = matrix[(square_i * 3) + ind_1][(square_j * 3) + ind_2]
- square_row.append(elem)
- square.append(square_row)
- return square
- def count_nulls_in_matrix(matrix: list[list[int]]) -> int:
- summ = 0
- for i in range(len(matrix)):
- for j in range(len(matrix[i])):
- if matrix[i][j] == 0:
- summ += 1
- return summ
- def check_if_matrix_right(matrix: list[list[int]]) -> bool:
- canon_numbers = get_canon_numbers()
- for i in range(len(matrix)):
- numbers_arr = []
- for j in range(len(matrix[i])):
- elem = matrix[i][j]
- if elem == 0:
- return False
- numbers_arr.append(elem)
- if not is_arrays_equal(numbers_arr, canon_numbers):
- return False
- for col_ind in range(len(matrix)):
- numbers_arr = []
- for row_ind in range(len(matrix[col_ind])):
- elem = matrix[row_ind][col_ind]
- numbers_arr.append(elem)
- if not is_arrays_equal(numbers_arr, canon_numbers):
- return False
- for square_i in range(3):
- for square_j in range(3):
- square = get_square(matrix, square_i * 3, square_j * 3)
- numbers_arr = []
- for i in range(3):
- for j in range(3):
- elem = square[i][j]
- numbers_arr.append(elem)
- if not is_arrays_equal(numbers_arr, canon_numbers):
- return False
- return True
- def get_canon_numbers() -> list[int]:
- return [i for i in range(1, 9 + 1)]
- def is_arrays_equal(arr1: list[int], arr2: list[int]) -> bool:
- if len(arr1) != len(arr2):
- return False
- for i in range(len(arr1)):
- if arr1[i] != arr2[i]:
- return False
- return True
- def sudoku(matrix):
- all_variants = generate_matrixes(matrix, 0)
- for variant in all_variants:
- if check_if_matrix_right(variant):
- return variant
- return matrix
- if __name__ == '__main__':
- matrix = [ [0, 0, 0, 8, 0, 0, 0, 0, 0],
- [4, 0, 0, 0, 1, 5, 0, 3, 0],
- [0, 2, 9, 0, 4, 0, 5, 1, 8],
- [0, 4, 0, 0, 0, 0, 1, 2, 0],
- [0, 0, 0, 6, 0, 2, 0, 0, 0],
- [0, 3, 2, 0, 0, 0, 0, 9, 0],
- [6, 9, 3, 0, 5, 0, 8, 7, 0],
- [0, 5, 0, 4, 8, 0, 0, 0, 1],
- [0, 0, 0, 0, 0, 3, 0, 0, 0] ]
- matrix_copy = [ [0, 0, 0, 8, 0, 0, 0, 0, 0],
- [4, 0, 0, 0, 1, 5, 0, 3, 0],
- [0, 2, 9, 0, 4, 0, 5, 1, 8],
- [0, 4, 0, 0, 0, 0, 1, 2, 0],
- [0, 0, 0, 6, 0, 2, 0, 0, 0],
- [0, 3, 2, 0, 0, 0, 0, 9, 0],
- [6, 9, 3, 0, 5, 0, 8, 7, 0],
- [0, 5, 0, 4, 8, 0, 0, 0, 1],
- [0, 0, 0, 0, 0, 3, 0, 0, 0] ]
- ans = sudoku(matrix)
- is_right = check_if_matrix_right(ans)
- print(is_right)
- print(ans)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement