数独回溯求解器错误

Question

好吧，我已经为此绞尽脑汁好几个小时了..

我的目标是编写一个使用回溯法的数独求解器，并使用 pygame 显示算法的进度。为此，我必须跟踪事件，我通过将它们附加到名为 registre 的列表来做到这一点，如代码所示：

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

我实际上成功了，大多数运行一切顺利。但有时，出于某种我无法确定的原因，会发生这种情况：

    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]]

打印的只是初始化网格、求解网格和 self.registre 中的前 20 个事件。为此运行 pygame 上的显示不起作用，一些数字自身重叠，而另一些则留空。我几乎可以肯定这不是显示问题，因为显示功能使用列表 registre 并且它对大多数其他运行工作正常。我也不明白这些事件。

完整脚本：

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])

问题的另一个实例：

[[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]]

如果你能帮助我，我将不胜感激。

Answer 1

添加重复生成网格的代码后，很明显您没有创建 Grid 的新实例，而是改变了现有的一。在此过程中，您应该注意完全重置状态。你只能部分地这样做，例如通过重置 t0。但是你没有重置 registre，所以当你打印前 20 项时，你实际上是在查看第一次尝试的日志，而不是成功的日志。

数独回溯求解器错误

Sudoku backtracking solver bug

python

debugging

sudoku

backtracking