Python Sudoku Backtracking Solved! But Not Returning Answer

Question

I have correctly made a sudoku backtracking solver. But now I need to get the solution, but for some reason I keep getting the original sudoku grid. The sudoku problem has a unique solution.

answer = []
count = 0
def solution(sudoku):
    global answer
    global count
    for y in range(9):
        for x in range(9):
            if sudoku[y][x] == 0: # Found an empty grid
                for n in range(1, 10):
                    if isPossible(x, y, n, sudoku):
                        sudoku[y][x] = n
                        solution(sudoku) # Recursion here
                        sudoku[y][x] = 0 # If no solution then reset the grid and go back
                solved = False
                return sudoku
    print("hi look at me")
    if count == 0:
        answer = list(sudoku)
        print(answer)
        count += 1
    return sudoku

hi = solution(board)
print(answer)
print(hi)

In this solution, answer = list(sudoku) will place the solution to my global variable also note that I used list() to make sure that global answer will not change when the sudoku parameter changes. I have made sure that this only occurs once. I understand that this backtracking will result in the original sudoku board because once the solution is solved this algorithm will set sudoku[y][x] = 0, effectively zeroing out the solution. But the unique solution is already stored in answer and when I try to print answer outside of the function I get the original unsolved sudoku board. So why is "answer" in the function gets the right solution but "answer" once outside the function gives me the original board? answer = list(sudoku) only occurs once and list() gives me a new list object so even if sudoku changes answer will never change, so how can after change at all? After hours of debugging I am genuinely stuck. How do I get the solution into something outside of the function?

Full code just in case

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

def isPossible(x, y, n, sudoku):
    if n in sudoku[y]: # Check if in row
        return False
    for i in range(0, 9):
        if n == sudoku[i][x]: # Check if in column
            return False
    y //= 3
    x //= 3
    for i in range(y*3, y*3 + 3): # Check if in squares
        for j in range(x*3, x*3 + 3):
            if n == sudoku[i][j]:
                return False
    return True

answer = []
count = 0
def solution(sudoku):
    global answer
    global count
    for y in range(9):
        for x in range(9):
            if sudoku[y][x] == 0: # Found an empty grid
                for n in range(1, 10):
                    if isPossible(x, y, n, sudoku):
                        sudoku[y][x] = n
                        solution(sudoku) # Recursion here
                        sudoku[y][x] = 0 # If no solution then reset the grid and go back
                return sudoku
    print("hi look at me")
    if count == 0:
        answer = list(sudoku)
        print(answer)
        count += 1
    return sudoku

hi = solution(board)
print(answer)
print(hi)

user_1405065 · Answer

The issue you have is that you have a nested list structure, and list(sudoku) only makes a shallow copy. The inner lists are still the same objects as the one that gets modified by later code. If you want a deep copy, you probably want to use the copy module's deepcopy function:

answer = copy.deepcopy(sudoku)

While this should solve your immediate problem of the backtracking scribbling all over your successful solution, it doesn't change the fact that your solver will keep on trying to find more solutions after you have already found one. To avoid that, you may want to change your code so that the value you return signals if you were successful or not. If you only return a solved board, or None if you didn't find one, you can use that to immediately end the search when the solution is found. And as a bonus, you don't need to use any global variables any more.

Here's what that should look like:

def solution(sudoku):                          # no more global variables needed
    for y in range(9):
        for x in range(9):
            if sudoku[y][x] == 0:
                for n in range(1, 10):
                    if isPossible(x, y, n, sudoku):
                        sudoku[y][x] = n
                        result = solution(sudoku)
                        if result is not None: # check if the recursion was successful or not
                            return result      # and stop searching if it was!
                        sudoku[y][x] = 0
                return None                    # signal failure
    return sudoku                              # signal success by returning the board

user_3066077 · Answer

The issue is you're only making a shallow copy of board so it continues to change with updates.

Shallow copy:

answer = list(sudoku)

One option is to use deepcopy instead:

answer = deepcopy(sudoku)

After replacing list with deepcopy in your code global retains the answer.

Future questions may be:

How to rewrite this code without using globals since globals are discouraged for simple code?
Is this code really backtracking or an exhaustive search?

Python Sudoku Backtracking Solved! But Not Returning Answer

2 Answers