Sudoku backtracking solver bug

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.

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.