How Backtracking works in Python

user_11675142 0
Viewed 306

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.

backtracking sudoku python
1 Answers

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
user_143680080
Related