问题标签 [backtracking]

我在网上搜索了解决 Haskell 中 n-queens 问题的不同解决方案，但找不到任何可以在 O(1) 时间内检查不安全位置的方法，比如为 / 对角线保留一个数组，为\ 对角线。

我发现的大多数解决方案只是将每个新皇后与之前的所有皇后进行对比。像这样的东西： http ://www.reddit.com/r/programming/comments/62j4m/nqueens_in_haskell/

在 Haskell 中实现这种“O(1) 方法”的最佳方法是什么？我不是在寻找任何“超级优化”的东西。只是某种方式来产生“这个对角线已经使用了吗？” 以功能方式排列。

更新：

感谢所有的答案，伙计们！我最初问这个问题的原因是因为我想解决一个更难的回溯问题。我知道如何用命令式语言来解决它，但不能轻易想到一个纯粹的函数式数据结构来完成这项工作。我认为皇后问题对于整个数据结构问题来说将是一个很好的模型（作为回溯问题:)），但这不是我真正的问题。

我实际上想找到一个允许 O(1) 随机访问并保存处于“初始”状态（自由线/对角线，在 n-queens 情况下）或处于“最终”状态（占用线/对角线），转换（自由到占用）为 O(1)。这可以在命令式语言中使用可变数组来实现，但我觉得更新值的限制​​只允许一个很好的纯函数数据结构（例如，与真正需要可变数组的快速排序相反）。

我认为某事的解决方案与在 Haskell 中使用不可变数组一样好，并且“main”函数看起来像我想要的那样：

不过，主要问题似乎是找到更好的数据结构，因为 Haskell 数组有 O(n) 更新。其他不错的建议没有达到神话般的 O(1) 圣杯：

• DiffArrays 接近但在回溯中搞砸了。他们实际上变得超级慢:(。
• STUArrays 与漂亮的功能回溯方法冲突，因此它们被丢弃。
• Maps 和 Sets 只有 O(log n) 更新。

我不确定是否有整体解决方案，但似乎很有希望。

更新：

我在 Trailer Arrays 中找到的最有前途的数据结构。基本上是一个 Haskell DiffArray，但是当你回溯时它会变异回来。

有哪些提供惰性列表处理的 OCaml 库？我正在寻找这些方面的东西：

与用于回溯StreamCamlp4 解析器的类型和语法糖集成会很好。

假设一个二维数组包含一个 9x9 数独网格，我的求解函数在哪里崩溃？我正在尝试使用简单的回溯方法来解决这个问题。谢谢！

即使改变了isSolved问题，我的解决方案似乎也陷入了无限循环。看起来我错过了一些基本案例步骤，但我不确定在哪里或为什么。我已经查看了类似的解决方案，但仍然无法确定问题所在。我只是想创建基本的求解器，不需要提高效率。谢谢您的帮助！

首先对不起我的英语。

我想在 Erlang 中使用回溯算法。它将作为解决部分填充数独的猜测。一个 9x9 数独存储为 81 个元素的列表，其中每个元素存储可以进入该单元格的可能数字。

对于 4x4 数独，我的初始解决方案如下所示：[[1],[3],[2],[4],[4],[2],[3],[1],[2,3], [4],[1],[2,3],[2,3],[1],[4],[2,3]]

这个数独有 2 个解决方案。我必须把它们都写出来。在达到最初的解决方案之后，我需要实现一个回溯算法，但我不知道如何实现。

我的想法是将固定元素写到一个名为fixedlist的新列表中，它将多解决方案单元格更改为[]。

对于上述示例，固定列表如下所示：[[1],[3],[2],[4],[4],[2],[3],[1],[],[4] ,[1],[],[],[1],[4],[]]

从这里我有一个“样本”，我在解决方案列表中寻找不等于 1 的最小长度，然后我尝试这个单元格的第一个可能的数字，然后我把它放到那个固定列表中。在这里，我有一个算法来更新单元格并检查它是否仍然是可解的数独。如果没有，我不知道如何退后一步尝试新的。我知道它的伪代码，我可以将它用于命令式语言，但不能用于 erlang。（prolog实际上实现了回溯算法，但是erlang没有）

任何的想法？

有一个袋子可以装X公斤。你会得到一系列的东西和它们的重量。如果没有答案，则打印 true 和每个东西的重量和 false

例子：

“Programming Challenges (The Programming Contest Training Manual)”可能是最好的算法练习书之一。我已经解决了前 11 个练习，但现在我遇到了“Crypt Kicker”问题：

Crypt Kicker
加密文本的一种常见但不安全的方法是置换字母表中的字母。换句话说，字母表中的每个字母在文本中始终被其他字母替换。为确保加密是可逆的，没有两个字母被同一个字母替换。

你的任务是解密几行编码的文本，假设每一行使用一组不同的替换，并且解密文本中的所有单词都来自已知单词的字典。

输入
输入由包含整数 n 的行组成，后跟 n 个小写单词，每行一个，按字母顺序排列。这 n 个单词组成了可能出现在解密文本中的单词字典。
字典后面是几行输入。如上所述，每一行都被加密。

字典中的单词不超过 1,000 个。没有单词超过 16 个字母。加密行仅包含小写字母和空格，长度不超过 80 个字符。

输出
解密每一行并将其打印到标准输出。如果有多种解决方案，任何一种都可以。
如果没有解决方案，请将字母表中的每个字母替换为星号。

示例输入6
和
dick
jane
puff
spot
yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

样本输出
dick and jane and puff and spot and yertle ...

我应该采取什么策略来解决这个问题？我正在考虑一个经典而残酷的回溯解决方案，但我试图避免这种情况，直到我找到更智能的东西。

PS：这与作业无关，我只是想提高我的整体技能。

我正在尝试解析 F# 类型语法。我开始编写 [F] Parsec 语法并遇到问题，因此我将语法简化为：

在遇到 FParsec 问题后，我转而使用 Parsec，因为我有一整章专门解释它。我的这个语法的代码是

问题是 Parsec 默认不回溯，所以

我尝试的第一件事是重新排序 typeP：

但这只是堆栈溢出，因为语法是左递归的——typeP 永远不会尝试identP，因为它会arrowP一遍又一遍地尝试。接下来我在各个地方进行了尝试try，例如：

但是我所做的一切似乎都没有改变（1）堆栈溢出或（2）在标识符后面不识别“->”的基本行为。

对于任何成功编写 Parsec 语法的人来说，我的错误可能是显而易见的。有人可以指出吗？

我被困在How to Design Programs 的扩展练习 28.2 上。我使用真值或假值的向量来表示板，而不是使用列表。这就是我所拥有的不起作用：

假设我有以下 Prolog 知识库：

如果我编写以下 C 代码：

它只会调用谓词“likes”一次，从而只产生“mary”。如何让它回溯并生成和打印所有结果？

谢谢，

我必须遍历一个矩阵并说出每种类型有多少个“特征区域”。

特征区域定义为值 n 或 >n 的元素相邻的区域。

例如，给定矩阵：

有一个类型 1 的单一特征区域，它等于原始矩阵：

类型 2 有两个特征区域：

以及类型 3 的一个特征区域：

因此，对于函数调用：

结果应该是

我还没有定义 countAreas，visit当我的函数没有更多可能的方块可以移动时，我被卡住了，并且没有进行正确的递归调用。我是函数式编程的新手，我仍然在摸索如何在这里实现回溯算法。看看我的代码，我能做些什么来改变它？