我意识到这个问题已经在这里讨论了很多，而且我已经阅读了所有内容。但是，我的程序不起作用。好吧，它解决了简单和中等难度的网格，但是当涉及到一些困难的谜题时，它似乎陷入了无限循环。
同样，我已经阅读了很多关于这个主题的文章，但我仍然无法理解为什么我的程序无法运行。如果您能向我解释一下，我将不胜感激。
我从一些有用的辅助函数开始，所以它们不是很重要，但我会发布它们——也许你也会给它们任何反馈
所以，我有一个整数列表列表:
[[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]]
无法解决。它尝试不同的数字并且不会停止 :(
最佳答案
首先，在 def explore 中，我不会有“如果解决了”。这意味着，当它没有解决时，你会做两次测试。相反，您可以在 while 循环之后只返回一个“return true”。然后，如果它解决了，它永远不会进入 while 循环并返回 true。
我还怀疑 pos = lst.index(sth) 可能有点慢。编写一个只返回最短列表的 pos 的函数可能会更好。如果它正在进行引用比较，可能不会有太大差异。我也很惊讶 choice() 没有在 int 上测试 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
未经测试但应该可以解决问题
现在仅查看您的代码很难诊断出了什么问题。我的建议是尝试将一些信息输出到文本文件。这样你就可以看到你的探索是否遇到了无限循环(它可能多次选择相同的最小集)，或者你的求解器只是花费了非常长的时间才能完成。如果是后者，即使没有输出也很难判断是不是有问题。另一种选择是让您的探索功能打印出一个“深度”，这样您就可以看到它是变得非常深，还是一直卡在深度 1。
编辑: 我怀疑最大的问题是您的探索非常昂贵。现在它天真地尝试了列表中所有未解决部分的每一种约束组合。一种优化是每次尝试数字时都执行“约束”。希望这将使您的探索不必深入，因为它会开始删除很多潜在列表。
关于python - 在 python 中具有约束和回溯的数独求解器，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29857679/