Если кто-то может взглянуть и помочь мне понять, почему он не работает, в основном я использую алгоритм обратного отслеживания, который пытается определить число в ячейке, и, если число может соответствовать, он перемещается в следующую пустую ячейку, и когда он находит ячейка, в которой ни одно из чисел от 1 до 9 не работает, возвращает go к последней сработавшей ячейке и поднимает его на 1, а если она не работает и достигает 9, она переходит к последней ячейке и так далее ... ошибка, которую я m get - функция, продолжающая возвращать false, не решая сетку
Функция, которая проверяет, может ли число go в ячейке, и может ли оно измениться, если не возвращает False-
def Valid(grid, num, x, y):
#Check row
for i in range(len(grid[y])):
if grid[i][x] == num:
return False
#Check column
for i in range(len(grid[y])):
if grid[y][i] == num:
return False
#Check 3x3
nx = x
ny = y
if x % 3 == 1:
nx -= 1
elif x % 3 == 2:
nx -= 2
if y % 3 == 1:
ny -= 1
elif y % 3 == 2:
ny -= 2
for i in range(3):
for j in range(3):
if grid[nx + i][ny + j] == num:
return False
grid[x][y] = num
return True
Функция, которая находит пустую ячейку -
def Find_empty(grid):
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == 0:
return (i, j)
return None
Функция решения -
def Solve(grid):
empty = Find_empty(grid)
if empty == None:
return True
print("Empty", empty)
for x in range(1, 10):
if Valid(grid, x, empty[0], empty[1]):
if Solve(grid):
return True
grid[empty[0]][empty[1]] = 0
print("F")
return False
Сетка, на которой я ее тестирую -
grid = [
[8, 7, 6, 9, 0, 0, 0, 0, 0], #0
[0, 1, 0, 0, 0, 6, 0, 0, 0], #1
[0, 4, 0, 3, 0, 5, 8, 0, 0], #2
[4, 0, 0, 0, 0, 0, 2, 1, 0], #3
[0, 9, 0, 5, 0, 0, 0, 0, 0], #4
[0, 5 ,0 ,0, 4, 0, 3, 0, 6], #5
[0, 2, 9, 0, 0, 0, 0, 0, 8], #6
[0, 0, 4, 6, 9, 0, 1, 7, 3], #7
[0, 0, 0, 0, 0, 1, 0, 0, 4] #8
]