Ok, I’ve been scratching my head over this for a few hours now..

My goal was to code a sudoku solver that uses the backtracking method and to show the progress of the algorithm using pygame. For this I have to keep track of the events, I did it by appending them to a list named `registre`

as is shown in the code:

def solver(self): self.t1 = time.time() if self.t1-self.t0 > self.solve_time_max: sys.exit(1) for i in range(self.grid.shape[0]): for j in range(self.grid.shape[1]): if self.grid[i][j]==0: for n in range(1,10): self.registre.append([n,i,j]) if self.verify(n,i,j): self.grid[i][j]=n self.solver() if 0 not in self.grid: break self.registre.append([0,i,j]) self.grid[i][j]=0 return self.grid

I actually succeeded and everything goes fine for most of the runs. But sometimes, for some reason I couldn’t identify, this happens :

print(une_grille.grid0) print(une_grille.grid) print(une_grille.registre[:20])

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

What is printed is simply the initialized grid, the solved grid and the first 20 events in `self.registre`

. For this run the displaying on pygame didn’t work, some numbers overlap themselves and others are left blank. I am almost sure it’s not a displaying problem since the displaying function uses the list `registre`

and it works just fine for most of the other runs. Also I don’t understand these events.

Complete script :

import numpy as np import random as rd import time import sys class Grid(): """ une Docstring """ def __init__(self, nval=15, dim=(9,9), tries_max=1000, init_time_max=5e-3, solve_time_max = 1): self.nval = nval+1 self.dim = dim self.t0 = 0 self.t1 = 0 self.tries_max = tries_max self.k = 0 self.init_time_max = init_time_max self.solve_time_max = solve_time_max self.registre = [] self.grid = self.create_grid() self.smthg = 0 def create_grid(self): for tries in range(self.tries_max): self.k = 0 if tries == self.tries_max -1: print(f"Tried {self.tries_max} times, I have failed") sys.exit(1) self.grid0 = np.zeros([self.dim[0],self.dim[1]], dtype=int) try: self.grid0 = self.initialize_board() except SystemExit: print(f"TRY #{tries}: Spent too much time initializing board. Re-trying.") continue self.grid = np.copy(self.grid0) try: self.t0 = time.time() self.grid = self.solver() if 0 not in self.grid: print(f"Found grid with solution after n = {tries+1} tries!") return self.grid else: print(f"TRY #{tries} converged to null solution") continue except SystemExit: print(f"TRY #{tries} too much time spent trying to solve current grid, continuing") continue print("Maximum tries reached") def initialize_board(self): for i in range(self.nval): rx = rd.randint(0, self.grid0.shape[0]-1) ry = rd.randint(0, self.grid0.shape[1]-1) cx = int(rx/3) cy = int(ry/3) time0 = time.time() while(self.grid0[rx][ry]==0): if time.time()-time0 > self.init_time_max: sys.exit(1) r = rd.randint(1, 9) if((r in self.grid0[rx,:]) or (r in self.grid0[:,ry]) or (r in self.grid0[3*cx:3*cx+3,3*cy:3*cy+3])): continue else: self.grid0[rx][ry] = r return self.grid0 def solver(self): self.t1 = time.time() if self.t1-self.t0 > self.solve_time_max: sys.exit(1) for i in range(self.grid.shape[0]): for j in range(self.grid.shape[1]): if self.grid[i][j]==0: for n in range(1,10): self.registre.append([n,i,j]) if self.verify(n,i,j): self.grid[i][j]=n self.solver() if 0 not in self.grid: break self.registre.append([0,i,j]) self.grid[i][j]=0 return self.grid def verify(self, number, x, y): cx = int(x/3) cy = int(y/3) if((number in self.grid[x,:]) or (number in self.grid[:,y]) or (number in self.grid[3*cx:3*cx+3,3*cy:3*cy+3])): return False return True game = Grid(nval = 35) print(game.grid) print(game.grid0) print(game.registre[:20])

Another instance of the issue :

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

I would really appreciate it if you could help me with this.

## Advertisement

## Answer

After you added the code that *repeats* the generation of grids, it becomes clear that you don’t create a new instance of `Grid`

, but mutate the existing one. In that process you should then take care to reset the state *completely*. You only do this partly, e.g. by resetting `t0`

. But you don’t reset `registre`

, and so when you print the first 20 items, you are actually looking at the log of the first attempt, not the successful one.