Backtracking algorithm that finds solutions for sudoku

Question

I'm studying the theory of algorithms and their possible resolutions methods.In this case I have some problems with backtracking. I want to write a function that fill a sudoku. But it doesn't print anything. Where is the error? The function defsett(i,j) take as input two numbers that are the coordinates of the number selected and set two integer (w and o) that are the starting points of the section 3x3 of the input number. Instead the sudoku function recursively tries to fill the matrix with the rules of sudoku.

# defsett = returns the coordinates of the first cell of the section 3x3 
# where is the cell [i,j]
def defsett(i,j):
    if(0<=i<=2):
        if(0<=j<=2):
            return (0,0)
        elif(3<=j<=5):
            return (0,3)
        elif(6<=j<=8):
            return (0,6)
    elif(3<=i<=5):
        if(0<=j<=2):
            return (3,0)
        elif(3<=j<=5):
            return (3,3)
        elif(6<=j<=8):
            return (3,6)
    else:
        if(0<=j<=2):
            return (6,0)
        elif(3<=j<=5):
            return (6,3)
        elif(6<=j<=8):
            return (6,6)
M = [[5,3,0,0,7,0,0,0,0],
     [6,0,0,1,9,5,0,0,0],
     [0,9,8,0,0,0,0,6,0],
     [8,0,0,0,6,0,0,0,3],
     [4,0,0,8,0,3,0,0,1],
     [7,0,0,0,2,0,0,0,6],
     [0,6,0,0,0,0,2,8,0],
     [0,0,0,4,1,9,0,0,5],
     [0,0,0,0,8,0,0,7,9]]

# n = matrix side
# i = index of rows
# j = index of cols

def sudoku(n,i,j,M):
        if(i==n):
            print(M)
        elif(j==n):
            j=0
            i=i+1
            sudoku(n,i,j,M)
        else:
            if(M[i][j]==0):
                for number in range(1,n+1):

                    xInRows = False
                    xInCols = False
                    xInSection = False

   # checking if number already present in this row 
                    for k in range(n): 
                        if (number == M[i][k]):
                            xInRows = True

   # checking if number already present in this cols 
                    for k in range(n):
                        if(number == M[k][j]):
                            xInCols = True

                    w,o=defsett(i,j) # first cell of this section

   # checking if number already present in this section 3x3
                    for t in range(w,w+3):
                        for b in range(o,o+3):
                            if(number == M[t][b]):
                                xInSection = True

                    if(not(xInRows) and not(xInCols) and not(xInSection)):
                        M[i][j] = x
                        sudoku(n,i,j+1,M)
            else:
                sudoku(n,i,j+1,M)
sudoku(9,0,0,M)
-----
For this input works:
M = [[5,3,0,0,7,0,0,0,0],
     [6,0,0,1,9,5,0,4,8],
     [1,9,8,3,4,2,5,6,7],
     [8,5,9,7,6,1,4,2,3],
     [4,2,6,8,5,3,7,9,1],
     [7,1,3,9,2,4,8,5,6],
     [9,6,1,5,3,7,2,8,4],
     [2,8,7,4,1,9,6,3,5],
     [3,4,5,0,8,6,1,7,9]]
For this doesn't:
M = [[5,3,0,0,7,0,0,0,0],
     [6,0,0,1,9,5,0,0,8],
     [1,9,8,3,4,2,5,6,7],
     [8,5,9,7,6,1,4,2,3],
     [4,2,6,8,5,3,7,9,1],
     [7,1,3,9,2,4,8,5,6],
     [9,6,1,5,3,7,2,8,4],
     [2,8,7,4,1,9,6,3,5],
     [3,4,5,0,8,6,1,7,9]]

Answer 1

The reason as to why nothing is printed is simple: sudoku() failed to progress far enough that i == 9 ever yields True. So lets analyse how that can happen...

1. i == 9 ⇒ exit with solution
2. i != 9 and j == 9 ⇒ recursion with next row; sudoku(9, i+1, 0, M)
3. i != 9 and j != 9
   1. M[i][j] != 0 ⇒ recursion with next column sudoku(9, i, j+1, M)
   2. M[i][j] == 0 ⇒ try to fit in a number
      1. found candidate number ⇒ set M[i][j] = number (not M[i][j] = x) and go into recursion with next column sudoku(9, i, j+1, M)

And that's the entire decision making process. This is M once sudoku() exits:

[[5, 3, 2, 6, 7, 8, 9, 4, 0],
 [6, 0, 0, 1, 9, 5, 0, 0, 8],
 [1, 9, 8, 3, 4, 2, 5, 6, 7],
 [8, 5, 9, 7, 6, 1, 4, 2, 3],
 [4, 2, 6, 8, 5, 3, 7, 9, 1],
 [7, 1, 3, 9, 2, 4, 8, 5, 6],
 [9, 6, 1, 5, 3, 7, 2, 8, 4],
 [2, 8, 7, 4, 1, 9, 6, 3, 5],
 [3, 4, 5, 0, 8, 6, 1, 7, 9]]

In order to understand what went wrong, imagine you're calling sudoku(9, 0, 8, M) after 4 was placed in the eighth column...

1 is the only number not yet placed in this row, but it is forbidden here, because it occures already in the fifth row (M[4][8]). sudoku(9, 0, 8, M) quits, since there are no other numbers to try. From here control moves up in the call stack, because noone is able to place 1 anywhere else. Why is 1 so important? Because all other numbers have been put somewhere in this row already and that is not changed while sudko() backtracks!

The fix is simple: Add a line after the recursion step where you had filled in a number, that undoes the change for proper backtracking.

(...)
                    if(not(xInRows) and not(xInCols) and not(xInSection)):
                        M[i][j] = x
                        sudoku(n,i,j+1,M)
                        M[i][j] = 0
(...)

That alone will make sudoku() finish for the given M. I won't guarantee that it will find a solution for any M though. ;-)