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)

Stael · Answer 1 · 2017-03-23T10:53:20.273

0

In place of a comment:

Your use of 'continue' is odd,

        if i in grid[x]:
            check = False
            continue  # here we break out to the next value of i
        for row in range(0,9):
            if i == grid[row][y]:
                check = False
                continue  # here we move to the next value of 'row' 
                          # which we would do anyway

I think that would mean in many cases that you would move on to

return alist

before you wanted to.

my only other comment is that your function returns 'alist' but in the recursion you never use that value (perhaps your relying on append? it's unclear to me)

edited Mar 23 '17 at 10:53

answered Mar 23 '17 at 10:41

Stael

2,619
15
19

i use continue, because i doesnt' meet the constraint of sudoku. In the row , column, or square there should not be the same number. – Seanie Lee Mar 23 '17 at 13:25
I don't think it's doing what you think it is, but it doesn't seem to be the main problem - i've added a second answer now that I've found out what was actually going on. – Stael Mar 23 '17 at 15:00

score 0 · Accepted Answer · edited May 23 '17 at 12:17

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.

backtracking sudoku and save all possible answer in list

2 Answers2