基于约束满足的数独求解器回溯迭代DFS

Question

我正在尝试用一个迭代DFS算法编写一个数独解算器，该算法具有回溯和约束满足

def sudoku_solver(sudoku):
    states = []
    ste_Hsh = set()
    visited = []
    novisited = 0
    states.append(sudoku)
    ste_Hsh.add(str(sudoku))
    visited.append(False)
    r = findRemaining(sudoku)
    while not all(visited):
        if isSolved(sudoku):
            return sudoku
        
        if not visited[novisited]:
            sudoku, r  = pickValAndProp(findNewPos(sudoku,r),sudoku.copy(),r,ste_Hsh) 
        else:
            try:
                novisited = len(visited) - visited[::-1].index(False) -1
            except:
                break
            sudoku = states[novisited]
        if isinstance(sudoku,int):
            visited[novisited] = True
            try:
                novisited = len(visited) - visited[::-1].index(False) -1
            except:
                break
            sudoku = states[novisited]
            r = findRemaining(sudoku)
            continue
        ste_Hsh.add(str(sudoku))
        if len(ste_Hsh) > len(states):
            if novisited == len(states)-1:
                states.append(sudoku)
                visited.append(False)
            else:
                states[novisited+1] = sudoku
                visited[novisited+1] = False
            novisited += 1
            
        
    return np.full((9,9),-1,dtype=int)

这是我的解算器函数

findRemaining()返回每行（r[2]）、列（r[1]）和正方形（3x3网格）（r[0]）的剩余可能值的列表

findNewPos()返回下一个要填充的位置，它通过查找具有最小可能值的单元格（使用该单元格所在的行、列和平方的剩余值的总长度的复合度量进行计算）来完成此操作

pickValAndProp是传播算法，请参见以下内容：

def pickValAndProp(new_pos,sudoku,r,ste_Hsh):
    try:
        val = 0
        tried = set()
        noOfStates = len(ste_Hsh)
        i = 0

        while noOfStates == len(ste_Hsh):

            val = r[1][new_pos[1]][i]
            if val in r[0][locateSquareOfPos(new_pos,sudoku)] and val in r[2][new_pos[0]]:
                sudoku[new_pos[0]][new_pos[1]] = val
                ste_Hsh.add(str(sudoku))
            else:
                tried.add(val)
                
                if(len(tried) == len(r[1][new_pos[1]])):
                    return (-1,-1)
            i+=1
        print("no of States :",noOfStates)      
        #remove from square
        r[0][locateSquareOfPos(new_pos,sudoku)].remove(val)
        #remove from col 
        r[1][new_pos[1]].remove(val)
        #remove from row
        r[2][new_pos[0]].remove(val)
                
        return (sudoku,r)
    except:
        return (-1,-1)

该算法在简单/中等问题上表现良好，但在困难问题上，它将永远持续下去。董事会独特状态的数量达到100000个

编辑：问题在于findNewPos()。我的启发是错误的

以下是更新版本：

def findNewPos(sudoku,r):
    new_pos = [-1,-1]
    no_r = 10
    deg_h = 100
    for i in range(sudoku.shape[0]):
        for j in range(sudoku.shape[1]):
            if sudoku[i][j] == 0:
                common = np.intersect1d(r[0][locateSquareOfPos([i,j],sudoku)]\
                    ,np.intersect1d(r[2][i],r[1][j]))
                if len(common) == 0:
                    return [-1,-1]
                if len(common) < no_r:
                    no_r = len(common)

                    deg_h = len(r[0][locateSquareOfPos(new_pos,sudoku)])\
                    +len(r[1][j]) + len(r[2][i])

                    new_pos = [i,j]
                    
                elif len(common) == no_r:

                    rmng = len(r[0][locateSquareOfPos(new_pos,sudoku)])\
                    +len(r[1][j]) + len(r[2][i])

                    if rmng < deg_h:
                        deg_h = rmng
                        new_pos = [i,j]

    return new_pos

现在所有的数独游戏都在解决，尽管速度很慢。我需要改进我的分阶段启发式（当有多个变量具有相同数量的剩余值时），我想使用度启发式。然而，我不确定这在数独的环境下是如何工作的