Решатель судоку с использованием обратного отслеживания ⇐ Python

[Anonymous]

Я использую этот код для решения судоку с использованием алгоритма возврата, но он, хотя и дает правильный ответ, сталкивается с ошибкой «превышен лимит памяти», когда я пытаюсь это проверить
Кажется, я где-то зациклился!
import numpy как np
def sudoku_solver_util(mat, Many, f_count):
if Many[0] >= 9 ** (81 - f_count):
возвращает False
для i в диапазоне (9):
для j в диапазоне (9):
if mat[j] == 0:
counter = 0
для k в диапазоне (1, 10):
counter += 1
many[0] + = 1
if is_safe(mat, i, j, k, 0, f_count, Many):
mat[j] = k
if sudoku_solver_util(mat, Many, f_count) :
вернуть True
count = np.count_nonzero(mat)
if Many[0] >= 9**(81-f_count):
вернуть False
mat [j] = 0
if counter == 9:
возвращает False
возвращает True
def row_is_safe(mat, i, j, k):
вернуть не k в mat[:]
def col_is_safe(mat, i, j, k):
вернуть не k в mat [:,j]
defgrid_is_safe(mat, i, j, k):
вернуть не k в small_sudoku(mat, i, j)
def is_safe(mat, i, j, k, counter, count, Many):
return row_is_safe(mat, i, j, k) и col_is_safe(mat, i, j, k) и Grid_is_safe(mat, i, j, k)
def small_sudoku(mat, i, j):
return mat[(i//3)*3:(i/ /3)*3+3, (j//3)*3:(j//3)*3+3]
def sudoku_solver(mat):
много = [0]
f_count = np.count_nonzero(mat)
if sudoku_solver_util(mat, Many, f_count):
return mat
else:
return np.zeros ((9,9))
ввод
mat = np.zeros((9,9))
для i в диапазоне (0,9):
mat = list(map(int, input().split()))
вывод
out_mat = sudoku_solver(mat)
для строки в out_mat:
print(" ".join(map(str, row.astype(int))))

Подробнее здесь: https://stackoverflow.com/questions/791 ... cktracking