CODEWITHSUNDEEP
pythonrecursionstacksudoku
Borut Flis
Borut Flis

Reputation: 16375

Understanding recursion and stacks in Python

I am developing a sudoku solver in Python. 

def backtrack(puzzle):
    x,y,candidates=findSquare(puzzle)
    if x==-1 and y==-1:
        return puzzle #stop condition
    while len(candidates[x][y])>0:
        puzzle[x][y]=candidates[x][y].pop()
        puzzler=backtrack(puzzle)
        if isValid(puzzler):
            return puzzler
    return False

It is an algorithm that basicaly makes guesses. When a guess is wrong it goes to the next guess(the while loop).

The problem I have is the variable puzzle, the sudoku puzzle. When a guess is wrong, the while loop goes to the next candidates. The variable puzzle now includes the modifications made by the further steps of recursion, even though the steps were a false guess. I don't understand this, the other variable are unique to each recursion stack, shouldn't puzzle stay the same as well.

Don't hesitate to ask for additional explanations.

Upvotes: 1

Views: 128

Answers (1)

9motom6
9motom6

Reputation: 66

The puzzle variable is a list. My guess is that every function backtrack uses the same puzzle (the same place in memory) because of shallow copy. Here is a nice answer about shallow vs deep copy in Python. What exactly is the difference between shallow copy, deepcopy and normal assignment operation?

More specifically the problem could be at line puzzler=backtrack(puzzle) I would try creating a deep copy of puzzle and give that to the recursion

Upvotes: 1

Related Questions