ruby - 高效的置换树算法

Question

我试图编写一种算法来解决任何数独问题。然而，我最初的方法是有缺陷的，因为我没有意识到一个结构良好的数独应该只有一个解决方案。

因此，生成的算法并未针对数独求解进行优化，而是更为通用:它递归地为当前数独布局生成每个可能允许的结果/布局。因此，该算法理论上可以找到空白数独的所有解决方案(但我/我们/人类可能不会看到输出)。

我的第一个问题是:对于这种类型的搜索算法，最佳方法是什么——如何改进我的算法？总体策略是:

• 在分支点尝试所有可能的解决方案
• 如果无法解决单元格，则终止分支
• 如果达到解决方案则终止分支

结构和方法改编自为解决 SICP 中的八皇后问题而概述的时间解耦解决方案 (https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html)，这似乎是一种回溯算法(“时间”状态被推送进入机器)，我的情况是这样吗？

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

期望的结果是执行类似 solve(sudoku).first(x) 的操作来检索前 x 个解决方案。 IE。解决方案存储为流/序列。我遇到的困难是递归生成嵌套的枚举，我正在努力寻找一种将强制方法传递到整个树的方法。

我在下面包含了关键代码，但完整的方法套件可以在这里找到: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>] 

Answer 1

您无需在每个分支点尝试所有可能的解决方案。您可以通过找到剩余选项数量最少的单元格并尝试那里的变体来做得更好。这样您就可以快速设置所有只剩下一个选项的单元格。当您需要尝试不同的解决方案时，您可能只有几个变体可以尝试 (2-3)，而不是所有的可能性，所以它应该更快。如果它们都不适用于该单元格，您可以停止，因为没有解决方案。