backtracking sudoku and save all possible answer in list

Question

I want to save all possible answers of sudoku, using backtracking but the added answer is just like the same as the sudoku problem. But when I print the "grid" when appending to the "alist" it is fine. How can I fix the problem?

def backtrack(grid,x,y,alist):
    if x == 9:

        alist.append(grid)
        print(grid)
        return alist

    v = grid[x][y]

    if v == 0:
        for i in range(1,10):

            check = True
            if i in grid[x]:
                check = False
                continue
            for row in range(0,9):
                if i == grid[row][y]:
                    check = False
                    continue

            for row in range(3*(x//3),3*(x//3)+3):
                for col in range(3*(y//3),3*(y//3)+3):
                    if i == grid[row][col]:
                        check = False
                        continue
            if check == True:
                grid[x][y]= i
                if y < 8:
                    backtrack(grid,x,y+1,alist)

                else:
                    backtrack(grid,x+1,0,alist)
        grid[x][y] = 0
        return alist
    else:
        if y< 8:
            backtrack(grid,x,y+1,alist)
        else:
            backtrack(grid,x+1,0,alist)

        return alist


problem = [[4, 0, 3, 0, 2, 0, 6, 0, 0],
                          [9, 6, 0, 3, 0, 0, 0, 0, 0],
                          [2, 0, 1, 8, 0, 6, 0, 9, 0],
                          [0, 0, 8, 1, 0, 2, 9, 0, 0],
                          [7, 2, 0, 0, 6, 0, 0, 0, 8],
                          [0, 0, 6, 7, 0, 8, 2, 0, 0],
                          [0, 0, 2, 6, 0, 9, 5, 0, 0],
                          [8, 0, 0, 2, 0, 3, 0, 0, 9],
                          [0, 0, 5, 0, 1, 0, 3, 0, 0]]
alist = []
for a in backtrack(problem,0,0,alist):
    print(a)

Answer 1

I'm adding a second answer because I've actually found the problem now. Although I stand by my previous comment that your use of continue is odd.

consider your variable grid because this is python that is an object, when you find a solution you append grid to alist but because python lists are mutable (I think that is the right term) when you later call grid[x][y] = 0 you change the object grid, which is referenced at the first position of alist.

Try this code:

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

alist = [grid, grid, grid]

grid[0][0] = "hello"
print alist

each grid in alist has been modified.

instead, you can create a copy of the grid object and append that copy to your alist see How to clone or copy a list? for options. eg:

import copy

...

...alist.append(copy.deepcopy(grid))

copy.copy doesn't seem to work, likely because you are using lists with lists, rather than a numpy array or something similar.