python-3.xreferencebacktrackingrecursive-backtracking

Not able to save the current state of variables in the global array in nested functions in Python (Very confusing title, please read description)


I have made this python program to solve a sudoku and save all its possible valid answers in an array and return it. But it is failing in doing so. The logic is perfect and is being executed perfectly. But the problem is that that in both the nested else in the solver function, I want to save the current situation of the board in allAns array, but am not able to do so. Everytime I tried, it saved the default value (one with the dots) in the allAns array. I tried using nonlocal variables, passing in the allAns array as a parameter and many more, but am unable to do so. Couldn't find anything of help on the web. This place is my last hope

def solveSudoku(board: list[list[str]]) -> None:
    allAns = []
    board1 = board.copy()
    def totalEle(i: int, j: int, allEle: list[int]):
        for b in range(9):
            if board[i][b] != '.':
                allEle[int(board[i][b]) - 1] = False
            if board[b][j] != '.':
                allEle[int(board[b][j]) - 1] = False
            boxI = (i // 3) * 3 + b // 3
            boxJ = (j // 3) * 3 + b % 3
            if board[boxI][boxJ] != '.':
                allEle[int(board[boxI][boxJ]) - 1] = False

    def solver(i: int, j: int):
        if board[i][j] == '.':
            cannotBe = [True for _ in range(9)]
            totalEle(i, j, cannotBe)
            for k in range(1, 10):
                if cannotBe[k-1]:
                    board[i][j] = str(k)
                    if j < 8:
                        solver(i, j + 1)
                    elif i < 8:
                        solver(i + 1, 0)
                    else:
                        for m in range(9):
                            for n in range(9):
                                board1[m][n] = board[m][n]
                        allAns.append(board1)
                    board[i][j] = '.'
        else:
            if j < 8:
                solver(i, j + 1)
            elif i < 8:
                solver(i + 1, 0)
            else:
                for m in range(9):
                    for n in range(9):
                        board1[m][n] = board[m][n]
                allAns.append(board1)
    solver(0, 0)
    print(allAns)
    return allAns

sudoku =   [["5","3",".",".","7",".",".",".","."],
            ["6",".",".","1","9","5",".",".","."],
            [".","9","8",".",".",".",".","6","."],
            ["8",".",".",".","6",".",".",".","3"],
            ["4",".",".","8",".","3",".",".","1"],
            ["7",".",".",".","2",".",".",".","6"],
            [".","6",".",".",".",".","2","8","."],
            [".",".",".","4","1","9",".",".","5"],
            [".",".",".",".","8",".",".","7","9"]]

allAnswers = solveSudoku(sudoku)

Solution

  • The issue is due to scope in a recursive function. You can use deepcopy().

    from copy import deepcopy
    def solveSudoku(board: list[list[str]]) -> None:
        allAns = []
        board1 = deepcopy(board)
        # etc...
    

    See this answer for more.