Backtracking is failing in SUDOKU

Question

I have been trying to implement Sudoku in Python, but the backtracking is not working at all. When I input a 4x4 grid of 0's, I get output, but most of the time it fails to provide the result for a 3x3. This test case progresses correctly until it reaches the last element of the second row.

import math

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

#solution=[[0 for x in range(4)] for y in range(4)]

N=9
row=0
col=0

def positionFound():
    global row,col
    for x in range(N):
        for y in range(N):
            if solution[x][y] is 0:
                row,col=x,y
                return row,col
    return False

def isSafe(row,col,num):
    global N
    for c in range(N):
        if solution[row][c] is num:
            return False
    for r in range(N):
        if solution[r][col] is num:
            return False
    r=row-row%int(math.sqrt(N))
    c=col-col%int(math.sqrt(N))

    for x in range(r,r+int(math.sqrt(N))):
        for y in range(c,c+int(math.sqrt(N))):
            if solution[x][y] is num:
                return False

    return True
back=1

def sudoku(solution):
    global row,col
    if positionFound() is False:
        print('SUCCESS')
        for x in solution:
            print(x)
        return True


    for number in range(1,N+1):
        if isSafe(row,col,number):
            solution[row][col]=number
            if sudoku(solution) is True:
                return True
            solution[row][col]=0


    return False


sudoku(solution)
for x in solution:
     print(x)

OUTPUT:

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

Answer 1

The reason your backtracking isn't working is that you haven't implemented backtracking. Once you fail to place a number in a given location, you have no provision to return your [row, col] cursor to the previous position. You need to involve a way to know what the previous filled position was and resume with the next legal number for that position. Your recursion holds previous board positions in the stack, but you've lost the cursor position -- and your re-try loop assumes that it gets reset.

One strong possibility is to make row and col local variables, keeping them coordinated with the solution grid they describe. Make them part of the parameter passing, so the stack maintains those values for you.