Why does my sudoku solution generator keeps giving the same solution?

user_16417347 0
Viewed 62

The code should be straight forward but I found that it works sometimes well and sometimes not at all. when trying to print the solutions immediately it works fine but when I try to store, use , or do anything else with them, the generator simply keeps giving the same solution over and over

def isvalid(grid,y,x,n): 
    for i in range(9):
        if i!=y and grid[i][x]==n:
            return False
        if i!=x and grid[y][i]==n:
            return False
    sy=3*(y//3)
    sx=3*(x//3)
    for dy in range(3) :
        for dx in range(3) :
            if sy+dy!=y and sx+dx!=x:
                if grid[sy+dy][sx+dx]==n: return False
    return True

def solve(grid):
    number_list = [1,2,3,4,5,6,7,8,9]
    for y in range(9):
        for x in range(9):
            if grid[y][x]==0:
                random.shuffle(number_list) 
                for i in number_list:
                    if isvalid(grid,y,x,i):
                        grid[y][x]=i
                        yield from solve(grid)
                        grid[y][x]=0
                return
    yield grid

with this code the first case works fine and prints different grids but in the #2 one the solutions are the same and the result is true

grid=[[0]*9 for x in range(9)]
s= solve(grid)
# 1
for i in s:
    print(i)
# 2
solutions=[]
for i,n in zip(s,range(3)):
    solutions.append(i)
print(solutions[0]==solutions[1])
backtracking sudoku generator python
1 Answers

Your code uses a single mutable data structure grid which the solve function modifies in place at each step. Every yield grid statement is simply returning a reference to this mutable object, so the list you collect is a list of references to the same thing, in its latest state.

Note: you can see your solutions point to the same object by checking:

print(solutions[0] is solutions[1])

Try yielding a deep copy of the grid each time (if you want to collect a list of them), or print the grids as they are generated rather than collecting them (edit: IIUC your print approach #1 currently shows different solutions as expected):

yield [[entry for entry in row] for row in grid]

This could be memory intensive especially when you start with an empty grid as you have done. Probably better to test with an example which has fewer solutions first.

user_90174550
Related