高效排列树算法

Question

我试图编写一个解决数独问题的算法。然而，我的原始方法存在缺陷，因为我没有意识到一个良好构造的数独只应该有一个解。

因此，所得到的算法并不是针对数独问题进行优化的，它更加通用：对于当前数独布局，它递归地生成每个可能被允许的结果/布局。因此，理论上，该算法可以找到空白数独的每个解（但我/我们/人类可能无法看到输出）。

我的第一个问题是：对于这种搜索算法，什么是最优的方法 - 如何改进我的算法？一般策略是：

- 在分支点尝试每个可能的解决方案 - 如果无法解决单元格，则终止该分支 - 如果已达到解决方案，则终止该分支

该结构和方法是从SICP中用于解决八皇后问题的时间分离解决方案中进行了调整（https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html），似乎这是一种回溯算法（将“时间”状态推入机器中），在我的情况下是否正确？

我的第二个问题是，如何使用Ruby >= 2.x的Lazy功能来生成可枚举对象以处理递归算法？

期望的结果是执行solve(sudoku).first(x)以检索前x个解决方案。即，这些解决方案被存储为流/序列。我遇到的困难是递归会生成嵌套的可枚举对象，我无法找到一种方法将force方法传递整个树。

下面是关键代码，但完整的方法套件可以在此处找到：https://gist.github.com/djtango/fe9322748cf8a055fc0e

def solve(sudoku)
  guess(simplify_sudoku(sudoku))
end

def guess(sudoku, row = 0, column = 0)
  return sudoku.flatten                 if end_of_grid?(row, column)
  return guess(sudoku, row + 1, 0)      if end_of_column?(column)
  return guess(sudoku, row, column + 1) if filled?(sudoku, row, column)
  return nil                            if insoluble?(sudoku, row, column)
  permissible_values(sudoku, row, column).map do |value|
    guess(update_sudoku(sudoku, value, row, column), row, column + 1)
  end
end

def simplify_sudoku(sudoku)
  return sudoku if no_easy_solutions?(sudoku)
  simplify_sudoku(fill_in(sudoku))
end

def fill_in(sudoku)
  new_sudoku = copy_sudoku(sudoku)
  new_sudoku.map.with_index do |row, row_index|
    row.map.with_index do |column, column_index|
      solution = permissible_values(new_sudoku, row_index, column_index)
      easy_and_not_filled?(solution, new_sudoku, row_index, column_index) ? [solution.first] : column
    end
  end
end

当试图实现惰性求值时，最自然的引入惰性方法的点是猜测方法，如下所示：

  permissible_values(sudoku, row, column).map do |value|
    guess(update_sudoku(sudoku, value, row, column), row, column + 1)
  end

但是在实现时，结果是：

solve(blank_sdk)
 => #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 7, 8, 9]>:map> 

solve(blank_sdk).first(10)
 => [#<Enumerator::Lazy: #<Enumerator::Lazy: [2, 3, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 3, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 7, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 7, 8]>:map>] 

solve(blank_sdk).first(1000000000000)
 => [#<Enumerator::Lazy: #<Enumerator::Lazy: [2, 3, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 3, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 4, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 5, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 6, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 7, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 8, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 7, 9]>:map>, #<Enumerator::Lazy: #<Enumerator::Lazy: [1, 2, 3, 4, 5, 6, 7, 8]>:map>] 

- djtango

---

投票关闭的人可能这样做是因为他们认为你的问题虽然有趣，但并不适合放在SO上，姊妹站点Code Review可能更适合，部分原因是后者需要工作代码，而SO主要用于非工作努力。我倾向于同意，但没有投票关闭。如果你在Code Review上发布这个问题，我相信你会得到几个富有洞见和精心制作的答案。 - Cary Swoveland

谢谢您的回复 - 我在 Code Review 上看了一下（我是编程和 SO 的新手），同意我的帖子更适合在那里发布。在寻找类似于这个主题的帖子时，我还能够找到新的话题来支持我的研究，即 Algorithm X/跳舞链接，以及更普遍地讲，确切覆盖问题的主题，这正是我正在寻找的！顺便说一句，我无法使此任务的枚举工作 - 这部分内容是否适合在 SO 上发布？ - djtango

Answer 1

您不需要在每个分支点尝试所有可能的解决方案。找到剩余选项最少的单元格并在那里尝试变体会更好。这样，您可以快速设置仅剩一个选项的所有单元格。当您需要尝试不同的解决方案时，您可能只需要尝试几种变体（2-3），而不是所有可能性，因此速度应该更快。如果其中没有一种适用于该单元格，则可以停止，因为没有解决方案。

- Sorin