How does Recursive Backtracking work? Computerphile sodoku solver

Question

I'm so confused by backtracking because when the recursive call returns, won't you replace the solution found by replacing the grid back to zero. So even if you find the solution would it not be erased because after calling the solve function you are canceling what you did by replacing the value back to zero. I get the fact that you are backtracking but on the final recursive call that contains all the correct values are you not just replacing everything to 0?

# grid = .....    # defined as a global value,
                  # a list of 9 lists, 9-long each
def solve():
    global grid
    for y in range (0, 9):
        for x in range (0, 9):
            if grid[y][x] == 0:
                for n in range(1,10):
                    if possible(y, x, n):
                        grid[y][x] = n
                        solve()
                        grid[y][x] = 0
                return

    # edit: missed this final line:
    print (np.matrix(grid))

This was the code on Computerphile video by Prof. Thorsten Altenkirch.

Answer 1

This is weird code, but should work with some adaptations:

def solve():
    global grid
    for y in range(0, 9):
        for x in range(0, 9):
            if grid[y][x] == 0:
                for n in range(1,10):
                    if possible(y, x, n):
                        grid[y][x] = n
                        if solve():
                            return True  # return without reset
                        grid[y][x] = 0
                return False  # exhausted all options
            return True  # this is the deepest and last call with no more zeroes

Answer 2

Here is part of my code:

vlist = PossibleValueAtPosition(row,col) # find possible value at location (row, col)

for v in vlist:             # try each possible value

    puzzle[row][col] = v

if SolvePuzzle(n+1)==True:  # n=81 means all filled then end loop

    return True             # if get a solution, you return True

    puzzle[row][col] = 0        # if above return true, this line will never run

    return False                # return False for each fail attemp

Main program should like this

if SolvePuzzle(0)==True:

    print(puzzle)

else:

    print('No solution!')

Answer 3

It's not the final recursive call that contains all the correct values, but (each of) the deepest. Yes, this code enumerates all the solutions to the puzzle with the given board grid, not just the first solution.

For each (y,x) place, if it's empty, we try to place there each of the numbers from 1 through 9 in turn. If the placement was possible on the board as it is so far, we recurse with the changed grid board.

At the deepest level of recursion there were no empty (y,x) places on the board. Therefore we slide through to the print statement. _{(It could also be replaced by yield True for example, to turn it into a generator. On each next value we'd get from that generator, we'd have a complete solution -- in the changed grid. And when the generator would get exhausted, the grid would be again in its original state.)}

When all the numbers from 1 through 9 have been tried, the current invocation has run its course. But the one above it in the recursion chain is waiting to continue its work trying to fill its (y,x) position. We must let it work on the same board it had before it invoked this invocation of solve(). And the only change on the board this invocation did was to change its (y,x) position's value from 0 to 1 through 9. So we must change it back to 0.

This means that the code could be restructured a little bit too, as

def solve():
    global grid
    for y in range (0, 9):
        for x in range (0, 9):     # for the first
            if grid[y][x] == 0:    # empty slot found:
                for n in range(1,10):  # try 1..9
                    if possible(y, x, n):
                        grid[y][x] = n
                        solve()        # and recurse
                # (move it here)
                grid[y][x] = 0     # restore
                return             # and return
    # no empty slots were found:
    #   we're at the deepest level of recursion and
    #   there are no more slots to fill:
    yield True     # was: print (np.matrix(grid))

Each invocation works only on one (y,x) location, the first empty position that it found by searching anew from the start on the changed board. This search is done by the first two nested loops on y and on x. That is a bit redundant; we know all the positions before this (y,x) are already filled. The code would be better restructured to pass the starting position (y,x) as a parameter to solve.

The paradigm of recursive backtracking is beautiful. Prolog is full of mystique, Haskell will dazzle you with cryptic monads talk (monads are actually just interpretable nestable data), but all it takes here are some nested loops, recursively created!

The paradigm is beautiful, but this code, not so much. A code's visual structure should reflect its true computational structure, but this code gives you an impression that the y-x- loops are the nested loops at work to create the backtracking structure, and they are not (they just implement a one-off linear search for the next empty space in the top-down left-to-right order).

That role is fulfilled by the n in range(1,10) loops. The y-x- loops should be stopped and exited explicitly when the empty space is found, to truly reflect in the code structure what is going on computationally, to make it apparent that the n in range(1,10) loop is not nested inside the y-x- loops, but comes in play after they finish their job.

Another problem is that it just assumes the validity of the numbers given to us in the grid before the very first call to solve(). That validity is never actually checked, only the validity of the numbers which we are placing in the empty cells is checked.

_{(note: previous versions of this answer were based on an erroneous reading of the code. there were some valid parts in them too. you can find them on the revisions list here).}