I am learning about backtracking and recursion and I don't understand (or can't visualize in my head) why my initial algorithm prints the board back into its original state, instead of printing the solution.
Here is my first attempt to solve the problem:
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)
After changing the solve function to the code below, I got the expected result.
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
Wouldn't the first exit point in the function "if not empty" be enough?
I also had a hard time wrapping my head around all these crazy recursion, but I kind of managed to understand. Your error is due to the line
grid[y][x] = 0
because this actually overwrites the correct board (try adding print_grid(grid) inside the condition if not empty:) after it is solved.
I think it is faster to understand the correct code instead of understanding why the original code did not work. I added some printing lines so it is easier to understand.
def solve(grid):
empty = find_empty(grid)
if not empty:
print("board completed")
return True
y, x = empty
for n in range(1, 10):
if possible(grid, y, x, n):
grid[y][x] = n
if solve(grid):
print("board is completed! do not reset anymore")
return True
print((y,x), " is not", n, " !!! reset this!!!")
grid[y][x] = 0
which prints:
(0, 4) is not 9 !!! reset this!!!
(0, 2) is not 3 !!! reset this!!!
(2, 1) is not 9 !!! reset this!!!
(2, 0) is not 3 !!! reset this!!!
(2, 1) is not 3 !!! reset this!!!
(3, 5) is not 8 !!! reset this!!!
(3, 3) is not 1 !!! reset this!!!
(4, 3) is not 7 !!! reset this!!!
(4, 1) is not 6 !!! reset this!!!
(4, 0) is not 2 !!! reset this!!!
(4, 8) is not 4 !!! reset this!!!
(4, 5) is not 2 !!! reset this!!!
(4, 3) is not 7 !!! reset this!!!
(4, 1) is not 6 !!! reset this!!!
(4, 0) is not 8 !!! reset this!!!
(3, 8) is not 1 !!! reset this!!!
(3, 5) is not 8 !!! reset this!!!
(3, 3) is not 9 !!! reset this!!!
(3, 1) is not 5 !!! reset this!!!
(3, 0) is not 3 !!! reset this!!!
(3, 5) is not 8 !!! reset this!!!
(3, 3) is not 1 !!! reset this!!!
(4, 3) is not 7 !!! reset this!!!
(4, 1) is not 6 !!! reset this!!!
(4, 0) is not 2 !!! reset this!!!
(4, 8) is not 4 !!! reset this!!!
(4, 5) is not 2 !!! reset this!!!
(4, 3) is not 7 !!! reset this!!!
(4, 1) is not 6 !!! reset this!!!
(4, 0) is not 8 !!! reset this!!!
(3, 8) is not 1 !!! reset this!!!
(3, 5) is not 8 !!! reset this!!!
(3, 3) is not 9 !!! reset this!!!
(3, 1) is not 3 !!! reset this!!!
(3, 0) is not 5 !!! reset this!!!
(3, 3) is not 1 !!! reset this!!!
(3, 3) is not 9 !!! reset this!!!
(3, 1) is not 3 !!! reset this!!!
(3, 5) is not 3 !!! reset this!!!
(3, 3) is not 1 !!! reset this!!!
(6, 5) is not 4 !!! reset this!!!
(6, 4) is not 8 !!! reset this!!!
(7, 3) is not 5 !!! reset this!!!
(7, 2) is not 8 !!! reset this!!!
(6, 6) is not 8 !!! reset this!!!
(6, 5) is not 4 !!! reset this!!!
(6, 4) is not 9 !!! reset this!!!
(6, 2) is not 6 !!! reset this!!!
board completed
basically, not empty is only going to be true when the board is filled correctly. Because if any of the number is in the wrong position, eventually that wrong number is going to be reset by grid[y][x] = 0, and tested with another number.
If the board is completed and if not empty: return True was executed, if solve(grid): will know that it shouldn't reset the board anymore, so it returns True. This will escape from the function, which means grid[y][x] = 0 line is going to be skipped.
If you don't understand, try printing in between each line so you can get the idea of what is going on. Hope this helped :)