How Backtracking works in Python

Question

I come up with this piece of code learning from Youtube. I use this to solve Sudoku by performing Backtracking.

import pandas as pd
import numpy as np


raw = pd.read_csv(r'C:\Users\Administrator\Dropbox\Python_Learning\debaisudoku.csv', header = None)
sudoku = np.nan_to_num(raw)

def possible(x,y,n):
    # global sudoku
    for i in range(0,9):
        if sudoku[i][y] == n:
            return False
    for i in range(0,9):
        if sudoku[x][i] == n:
            return False
        x0 = (x//3) * 3
        y0 = (y//3) * 3
    for i in range(0,3):
        for j in range(0,3):
            if sudoku[x0+i][y0+j] == n:
                return False
    return True

def solve():
    # global sudoku
    for x in range(9):
        for y in range(9):
            if sudoku[x][y] == 0:
                for n in range(1,10):
                    if possible(x,y,n):
                        sudoku[x][y] = n
                        if solve(): return True
                    sudoku[x][y] = 0
                return False
    print(sudoku)
solve()

Everything is absolutely fine and I understand the code except these lines of code:

    if possible(x,y,n):
        sudoku[x][y] = n
        if solve(): return True
    sudoku[x][y] = 0
return False

How Python Runs, Loop, and Remembers the position then continue counting last used number? By the way, if possible, please show me how to perform Backtracking in VBA. I've tried goto with if condition but nothing works.

Thank you so much, I appreciate any answers.

This is the whole principle of recursion. See [this](https://stackoverflow.com/questions/11693819/understanding-recursion-in-python), [this](https://stackoverflow.com/questions/52578602/how-do-a-python-recursive-function-works-for-tri-recursion-function), [this](https://stackoverflow.com/questions/30214531/basics-of-recursion-in-python) .... — trincot, Feb 24 '20 at 08:55
@trincot could you please explain where does the `return False` from `solve()` bring the code? At what point is it returning to? Is the nested x,y for loop of `slove()` starting all over again? — Alexander Cska, Dec 06 '20 at 13:24
When the function returns (for instance with `return False`), execution returns to the caller. The caller is where you have `solve()`. If the return value is False, then the `if` block where `solve` is the condition, will not be executed, and so execution *continues* (not restarts) with `sudoku[x][y] = 0` and the *rest* of the iterations of the `for` loop there... — trincot, Dec 06 '20 at 14:19
@trincot thank you for your reply. I don't understand how it goes back one step. If after `return False` the nested loop just continues, we would jump to the next point, having left a zero. I find this really confusing :( — Alexander Cska, Dec 06 '20 at 16:46
The zero is just the "undo" action that corresponds to the "move" that apparently didn't bring a solution via the recursive call (since it returned False). The next iteration of the `for` loop is necessary to try an alternative "move", again initiating a recursive call. If also that call returns False, and the loop has no more iterations, then also this function execution will return False to its own caller. — trincot, Dec 06 '20 at 17:09
@trincot I really appreciate your answers and patience. I put a `print "Back",x,y,n` before `sudoku[x][y]=0` and `print "start from",x,y` before `if sudoku[x][y]==0`. It looks, that sometimes it stars the loop from the beginning`x=0 and y=0`. ans sometimes it prints `Start from 3 8, back 3 7 6 back 3 6 7,back 3 3 5`. It reaches 3 8, fails and starts going back. So `return True` starts the nested loop with `x=0,y=0`. I still don't understand how it loops backward, when the recusrive call fails (in this example `y` goes backwards). — Alexander Cska, Dec 06 '20 at 18:57
It does not loop backward. But realise that each recursive execution of the function `solve` has its own variables, and its own execution context. So if you make a recursive call, that call will execute its own `for` loop from the start. If ever it performs a `return`, you backtrack to the other instance of the function, the one that made the recursive call. *That* one was in the middle of looping, and so it *continues* its loop from where it was before making the recursive call. Don't confuse the different loops: there is one at each level in the recursion tree. — trincot, Dec 06 '20 at 19:01
@trincot If i get it right, each instance has its own 'scope' with local instances of the variables. When returning, the function "jumps" to 'older scopes', which mimics "going backwards in time". — Alexander Cska, Dec 06 '20 at 19:49

score 1 · Accepted Answer · answered Sep 30 '20 at 14:06

I've have been trying it too within VBA after I saw the computerphile episode on youtube.

I guess if you want to "return" within VBA you need to make use of the "Exit function" functionality.

This code worked for me when using the first 9*9 cells as a grid in an excel sheet, after acknowledging the messagebox the sudoku will reset itself, I have no idea yet why this happens.

If anyone knows a cleaner way of coding this I would be glad to know, hope this helps you!

Function possible(y, x, n) As Boolean
    For i = 1 To 9
        If Cells(y, i) = n Then
        possible = False
        Exit Function
        End If
    Next i
    For i = 1 To 9
        If Cells(i, x) = n Then
        possible = False
        Exit Function
        End If
    Next i

x0 = ((x - 1) \ 3) * 3
y0 = ((y - 1) \ 3) * 3
For i = 1 To 3
   For j = 1 To 3
    If Cells(y0 + i, x0 + j) = n Then
    possible = False
    Exit Function
    End If
    Next j
  Next i
possible = True

End Function

Function solve()


For y = 1 To 9
    For x = 1 To 9
        If Cells(y, x).Value = 0 Then
            For n = 1 To 10
                Debug.Print (n)
                If n = 10 Then
                    Exit Function
                End If
                    If possible(y, x, n) = True Then
                        Cells(y, x).Value = n
                        solve
                        Cells(y, x).Value = 0
                    End If
            Next n
        End If
    Next x
Next y

MsgBox ("solved!")

End Function

Sub solve_sudoku()
solve
End Sub

It really works. Thank you so very much. The key here is Exit Function — Appscript.me, Oct 06 '20 at 05:15

How Backtracking works in Python

1 Answers1