Python中带有约束和回溯的数独求解器

Question

我知道这个问题在这里讨论过很多次，我已经阅读了所有的内容。然而，我的程序不起作用。它可以解决容易和中等难度的网格，但当涉及一些困难的谜题时，它似乎进入了一个无限循环。

再次，我已经阅读了关于此主题的许多文章，但仍然无法理解为什么我的程序无法正常工作。如果你能向我解释一下，我将非常感激。

首先，我有一些辅助函数，它们可以完成工作，所以它们并不是非常重要，但我会发布它们 - 也许您也会对它们提出任何反馈。

所以，我有一系列带有整数的列表：

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

首先，我定义一些辅助函数

from copy import deepcopy

def nice_print(grid): #just printing tool
    for line in grid:
        print(line)

def box(row,col,grid): #returns a list of numbers that are in the same box 
    row = (row // 3)*3 #with grid[row][col]
    col = (col // 3)*3
    return grid[line][row:row+3:]+grid[line+1][row:row+3:]+grid[line+2][row:row+3:]

现在我需要检查是否有任何数字可以轻松地放入网格中。

def constraints(grid):
    ngrid = deepcopy(grid)

    #in every cell with '0' i put a set{1..9}
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                ngrid[i][j] = set(range(1,10))

    #checking all conditions
    for k in range(81):
        for i in range(9):
            for j in range(9):
                if type(ngrid[i][j]) == set:
                    #square
                    if not ngrid[i][j].isdisjoint(set(box(i,j,grid))):
                        ngrid[i][j].difference_update(set(box(i,j,grid)))
                    #line
                    if not ngrid[i][j].isdisjoint(set(grid[i])):
                        ngrid[i][j].difference_update(set(grid[i]))  
                    #row
                    if not ngrid[i][j].isdisjoint(set(list(zip(*grid))[j])):
                        ngrid[i][j].difference_update(set(list(zip(*grid))[j]))   

                    #if there is the last remaining number i put it in the
                    #first grid and change the type of ngrid's cell to int
                    if len(ngrid[i][j]) == 1:
                        grid[i][j] = list(ngrid[i][j])[0]
                        ngrid[i][j] = list(ngrid[i][j])[0]

    #i parse from set&int to string
    for i in range(9):
        for j in range(9):
            if type(ngrid[i][j])==set:
                grid[i][j]=''
                for item in ngrid[i][j]:
                    grid[i][j]+=str(item)
            else:
                grid[i][j]=str(grid[i][j])            
    return grid

然后我定义了需要解决的问题...

def solved(grid):
    ans = True
    for num in range(1,10):
        num=str(num)
        #line
        for line in grid:
            if line.count(num) != 1:
                ans = False
                break
        #row
        for row in list(zip(*grid)):
            if row.count(num) != 1:
                ans = False
                break
        #square
        for i in [0,3,6]:
            for j in [0,3,6]:
                if box(i,j,grid).count(num) != 1:
                    ans = False
                    break
    return ans

现在我定义一些更多的辅助函数。

def grid_to_list(grid):
    lst = []
    for line in grid:
        lst+=line
    return lst

def parse_coordinate(s):
    row = s // 9
    col = s % 9
    return row,col

def choice(x):
    if len(x) > 1:
        return len(x)
    else:
        return 10

def check_constraints(grid,value,row,col):
    ans = True
    if grid[row].count(value) > 0:
        ans = False
    if list(zip(*grid)).count(value) > 0:
        ans = False
    if box(row,col,grid).count(value) > 0:
        ans = False
    return ans

最后我们来到了这个故事的主要部分 -- 回溯

def explore(grid):
    if solved(grid):
        return True #YAY!!!
    else:
        while not solved(grid):
            lst = grid_to_list(grid)   #i parse grid to list because i need
            sth = min(*lst,key=choice) #to find the cell with min length
            pos = lst.index(sth)
            sth = lst[pos]
            row,col = parse_coordinate(pos)
            for n in sth: 
                if check_constraints(grid,n,row,col): #if it's safe to place
                    grid[row][col] = n                #sth in grid[row][col]
                    if explore(grid):                 #i put it there and
                        return True                   #continue exploring
                    grid[row][col]=sth #if this doesn't work i return to the cell the previous value
            return False

一些其他的功能：将其重新组合

def str_to_int(grid):
    for i in range(9):
        for j in range(9):
            grid[i][j]=int(grid[i][j])
    return grid

def solve(grid):
    grid = constraints(grid)
    if explore(grid):
        nice_print(str_to_int(grid))
    else:
        print("there seems to be a problem")

因此，我的程序针对上述方格返回以下解决方案：

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

但是这个网格

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

这个问题IT无法解决。它会尝试不同的数字，但是无法停止 :(

- Lazy Daisy

Answer 1

首先，在def explore中，我不会使用'if solved.'这意味着当它没有解决方案时，您需要进行两次测试。相反，您可以在while循环后只需拥有'return true'。然后，如果已解决，它将永远不会进入while循环并返回true。

我还怀疑pos = lst.index(sth)可能有点慢。编写一个仅返回最短列表的pos函数可能更好。如果正在执行引用比较，则可能没有太大区别。我也很惊讶choice()没有在测试len()时出错。这个辅助函数可能会使代码更清晰：

def find_min_list(grid):
    minRow = 0
    minCol = 0
    minLength = 10

    for i in range(10):
        for j in range(10):
            if type(grid[i][j]) is list and len(grid[i][j]) < minLength:
                minLength = len(grid[i][j])
                minRow = i
                minCol = j

    return minRow, minCol

该方法未经测试，但应该能解决问题。

目前仅通过查看代码很难诊断故障。建议输出一些信息到文本文件中，这样您就可以看到是否存在无限循环的问题（它可能会多次选择相同的最小设置），或者您的求解器只需要花费非常长的时间才能完成。如果是后者，则很难确定是否存在问题。另一种选择是让您的explore函数打印出“深度”，这样您就可以看到它是否非常深，或者不断卡在深度1。

编辑: 我怀疑问题的关键是您的explore非常昂贵。现在，它天真地尝试了所有未解决部分列表上的约束组合。优化之一就是每次尝试一个数字时都执行“约束”。这将希望使您的探索不必深入到那么深，因为它会开始消除许多潜在的列表。

- Psymunn

---

非常感谢！在观察我的程序运行时，我意识到它在某些单元格中放置了一些数字，即使这些数字已经存在。所以问题出在检查约束条件的函数上！现在我已经修复了所有问题，再次感谢 :) - Lazy Daisy