时间戳

首页 > 解决方案 > 如何改进 Python 中的回溯数独求解算法？

python - 如何改进 Python 中的回溯数独求解算法？

问题描述

我用 Python 写了一个回溯数独求解算法。它解决了这样的二维数组（零表示“空字段”）：

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

像这样：

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

但是对于“硬”数独（开头有很多零），它非常慢。该算法大约需要 9 秒来解决上述数独问题。这比我开始时（90 秒）要好得多，但仍然很慢。

我认为可以以某种方式改进/替换“深度复制”（因为它在下面的示例中执行了 103.073 次），但我的基本方法较慢..

我听说过 0.01 秒的 C/C++ 解决方案，但我不确定这些是否是某种数学解决方案的回溯算法......

这是我的整个算法，有 2 个示例数独：

from copy import deepcopy

def is_sol_row(mat,row,val):
  m = len(mat)
  for i in range(m):
    if mat[row][i] == val:
      return False
  return True

def is_sol_col(mat,col,val):
  m = len(mat)
  for i in range(m):
    if mat[i][col] == val:
      return False
  return True

def is_sol_block(mat,row,col,val):
  rainbow = [0,0,0,3,3,3,6,6,6]
  i = rainbow[row]
  j = rainbow[col]
  elements = {
    mat[i + 0][j + 0], mat[i + 1][j + 0], mat[i + 2][j + 0],
    mat[i + 0][j + 1], mat[i + 1][j + 1], mat[i + 2][j + 1],
    mat[i + 0][j + 2], mat[i + 1][j + 2], mat[i + 2][j + 2],
  }
  if val in elements:
    return False
  return True

def is_sol(mat,row,col,val):
  return is_sol_row(mat,row,val) and is_sol_col(mat,col,val) and is_sol_block(mat,row,col,val)

def findAllZeroIndizes(mat):
  m = len(mat)
  indizes = []
  for i in range(m):
    for j in range(m):
      if mat[i][j] == 0:
        indizes.append((i,j))
  return indizes

def sudoku(mat):
  q = [(mat,0)]
  zeroIndizes = findAllZeroIndizes(mat)
  while q:
    t,numSolvedIndizes = q.pop()
    if numSolvedIndizes == len(zeroIndizes):
      return t
    else:
      i,j = zeroIndizes[numSolvedIndizes]
      for k in range(1,10):
        if is_sol(t,i,j,k):
          newt = deepcopy(t)
          newt[i][j] = k
          q.append((newt,numSolvedIndizes+1))
  return False


mat = [
  [7, 0, 0, 0, 0, 9, 0, 0, 3],
  [0, 9, 0, 1, 0, 0, 8, 0, 0],
  [0, 1, 0, 0, 0, 7, 0, 0, 0],

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

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

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

print(sudoku(mat))

标签： pythonalgorithmruntimesudoku

解决方案

最大的时间损失是，对于每个未平仓头寸，您尝试九位数字中的每一个，而没有了解任何有关尝试的信息。您的测试网格有 56 个开放网格位置，因此您所做的任何事情都会通过该镜头放大。一点预处理将有很长的路要走。例如，列出每行和每列中的可用数字。适当地键入它，并将其用于搜索而不是 range(m)。

另一种技术是应用简单的算法来制作琐碎的放置，因为它们变得可用。例如，您可以快速导出1左上块中的 ，以及块7的左列和中间列中缺少的 s。仅此一项就将求解时间缩短了一半。无论您对选定空心方块中的数字进行单一选择，或者选定的数字可以放置在特定的行/列/块中的哪个位置，然后在进行详尽的回溯之前进行该放置。

推荐阅读