How Does Recursive Backtracking Work? Computerphile Sodoku Solver

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 w

Solution 1:

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

defsolve():
    global grid
    for y inrange(0, 9):
        for x inrange(0, 9):
            if grid[y][x] == 0:
                for n inrange(1,10):
                    if possible(y, x, n):
                        grid[y][x] = n
                        if solve():
                            returnTrue# return without reset
                        grid[y][x] = 0returnFalse# exhausted all optionsreturnTrue# this is the deepest and last call with no more zeroes

Solution 2:

Here is part of my code:

vlist = PossibleValueAtPosition(row,col) # find possible valueat 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 thenend loop

    returnTrue             # if get a solution, you returnTrue

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

    returnFalse                # returnFalseforeach fail attemp

Main program should like this

if SolvePuzzle(0)==True:

    print(puzzle)

else:

    print('No solution!')

Solution 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 changedgrid. 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

defsolve():
    global grid
    for y inrange (0, 9):
        for x inrange (0, 9):     # for the firstif grid[y][x] == 0:    # empty slot found:for n inrange(1,10):  # try 1..9if possible(y, x, n):
                        grid[y][x] = n
                        solve()        # and recurse# (move it here)
                grid[y][x] = 0# restorereturn# and return# no empty slots were found:#   we're at the deepest level of recursion and#   there are no more slots to fill:yieldTrue# 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).}