Я узнаю о возврате и рекурсии, и я не понимаю (или не могу представить себе в голове), почему мой первоначальный алгоритм выводит плату обратно в исходное состояние вместо печати решения.
Вот моя первая попытка решить проблему:
grid = [
[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]
]
def print_grid(grid):
rows = len(grid)
cols = len(grid[0])
for y in range(rows):
if y % 3 == 0 and y != 0:
print("- " * (cols + 3))
for x in range(cols):
if x % 3 == 0 and x != 0:
print(" | ", end="")
if x == 8:
print(grid[y][x])
else:
print(str(grid[y][x]) + " ", end="")
def find_empty(grid):
for y in range(9):
for x in range(9):
if grid[y][x] == 0:
return (y, x)
def possible(grid, y, x, n):
# check rows
for i in range(9):
if grid[i][x] == n:
return False
# check cols
for i in range(9):
if grid[y][i] == n:
return False
# check subgrid
y0 = (y // 3) * 3
x0 = (x // 3) * 3
for i in range(3):
for j in range(3):
if grid[y0+i][x0+j] == n:
return False
return True
def solve(grid):
empty = find_empty(grid)
if not empty:
return True
y, x = empty
for n in range(1, 10):
if possible(grid, y, x, n):
grid[y][x] = n
solve(grid)
grid[y][x] = 0
solve(grid)
print_grid(grid)
После изменения функции решения на приведенный ниже код я получил ожидаемый результат.
def solve(grid):
empty = find_empty(grid)
if not empty:
return True
y, x = empty
for n in range(1, 10):
if possible(grid, y, x, n):
grid[y][x] = n
# changed this part
if solve(grid):
return True
grid[y][x] = 0
Не первый Достаточно ли точки выхода в функции «если не пусто»?