部分回溯搜索的通用算法
General algorithm for partial backtracking search
回溯搜索是一种众所周知的问题解决技术，它通过变量赋值的所有可能组合重复出现以寻找有效的解决方案。将通用算法抽象为简洁的高阶函数：https://en.wikipedia.org/wiki/Backtracking
有些问题需要部分回溯，也就是说，它们混合了不知道的非确定性（有一个选择，这很重要，如果你得到它错了你必须回溯）和不关心非确定性（有一个选择，这并不重要，也许重要的是你需要多长时间才能找到解决方案，但不是为了它的正确性，你不必回溯）。
例如考虑可以用 the DPLL algorithm 解决的布尔可满足性问题。如果你试图用一般的回溯算法来表示，结果不仅会通过所有 2^N 变量赋值（这在一般情况下很遗憾是必要的）重复出现，而且所有 N！尝试变量的顺序（完全不必要且效率低下）。
是否有部分回溯的通用算法？一个简洁的高阶函数，它为 don't-know 和 don't-care 选择接受函数参数？
如果我没理解错的话，你问的是树搜索中的 symmetry-breaking。在你给出的具体例子中，变量赋值列表的所有排列都是等价的。
对称性将是 domain-specific。 more-general 修剪搜索树的技术也是如此，通过 short-circuiting 和热切的回溯。我使用了一些 symmetry-breaking 概括的技巧。
一种是按规范顺序搜索问题space。如果设置变量 10 的分支只尝试变量 11、12 及以上，而不尝试变量 9、8 或 7，则它不会搜索相同解决方案的任何排列。它只会测试排列唯一的解决方案。 （在 SAT-solving 的特定情况下，这可能会排除最佳搜索顺序 — 尽管您可以 re-order 任意变量。）
另一种方法是进行测试，确保任何等价 class 中只有一个不同的解决方案会通过，最好是可以在搜索树顶部附近检查的解决方案。 classic 的例子是，在 8 皇后问题中，检查您首先看的行中的皇后是在棋盘的左侧还是右侧。她在右边的任何解决方案都是她在左边的另一个解决方案的 mirror-image，因此您可以将搜索 space 减半。 （对于那个问题，你实际上可以做得比这更好。）如果你只需要测试可满足性，你可以使用一个过滤器，它只保证，如果存在任何解决方案，至少有一个解决方案将通过。
如果你的内存够大，你也可以存储一组已经搜索过的分支，然后检查你正在考虑是否搜索的分支是否等同于该集合中已有的分支。这对于具有大量对称性的搜索 space 比具有大量独特的解决方案直至对称性的搜索更实用。
回溯搜索是一种众所周知的问题解决技术，它通过变量赋值的所有可能组合重复出现以寻找有效的解决方案。将通用算法抽象为简洁的高阶函数：https://en.wikipedia.org/wiki/Backtracking
有些问题需要部分回溯，也就是说，它们混合了不知道的非确定性（有一个选择，这很重要，如果你得到它错了你必须回溯）和不关心非确定性（有一个选择，这并不重要，也许重要的是你需要多长时间才能找到解决方案，但不是为了它的正确性，你不必回溯）。
例如考虑可以用 the DPLL algorithm 解决的布尔可满足性问题。如果你试图用一般的回溯算法来表示，结果不仅会通过所有 2^N 变量赋值（这在一般情况下很遗憾是必要的）重复出现，而且所有 N！尝试变量的顺序（完全不必要且效率低下）。
是否有部分回溯的通用算法？一个简洁的高阶函数，它为 don't-know 和 don't-care 选择接受函数参数？
如果我没理解错的话，你问的是树搜索中的 symmetry-breaking。在你给出的具体例子中，变量赋值列表的所有排列都是等价的。
对称性将是 domain-specific。 more-general 修剪搜索树的技术也是如此，通过 short-circuiting 和热切的回溯。我使用了一些 symmetry-breaking 概括的技巧。
一种是按规范顺序搜索问题space。如果设置变量 10 的分支只尝试变量 11、12 及以上，而不尝试变量 9、8 或 7，则它不会搜索相同解决方案的任何排列。它只会测试排列唯一的解决方案。 （在 SAT-solving 的特定情况下，这可能会排除最佳搜索顺序 — 尽管您可以 re-order 任意变量。）
另一种方法是进行测试，确保任何等价 class 中只有一个不同的解决方案会通过，最好是可以在搜索树顶部附近检查的解决方案。 classic 的例子是，在 8 皇后问题中，检查您首先看的行中的皇后是在棋盘的左侧还是右侧。她在右边的任何解决方案都是她在左边的另一个解决方案的 mirror-image，因此您可以将搜索 space 减半。 （对于那个问题，你实际上可以做得比这更好。）如果你只需要测试可满足性，你可以使用一个过滤器，它只保证，如果存在任何解决方案，至少有一个解决方案将通过。
如果你的内存够大，你也可以存储一组已经搜索过的分支，然后检查你正在考虑是否搜索的分支是否等同于该集合中已有的分支。这对于具有大量对称性的搜索 space 比具有大量独特的解决方案直至对称性的搜索更实用。