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.