问题标签 [recursive-backtracking]

我最近提取了一个 C 程序 ( https://repl.it/Klpv )，它在 8 x 8 板上搜索骑士之旅。我用 JavaScript 重新编写了程序（因为我更了解 JS），然后我修改了程序，以便可以在任何给定的板尺寸上搜索解决方案。

目前，它使用带有回溯的递归算法来打印它找到的第一个解决方案。然后它停止。原始 C 程序中的一条评论说该程序将打印一个可行的解决方案，但我的目标是打印所有（或可定制数量的）解决方案。我已经尝试稍微修改程序的“返回”命令，以便我可以让它打印多个解决方案，但我似乎无法做到这一点。谁能帮我吗？

这将打印到控制台：

编辑：我找到了一个可以做到这一点的 C++ 程序。https://repl.it/L4Pf不再需要帮助！

在打印出找到的第一个解决方案后，我想打印找到第一个解决方案所花费的时间，如下所示。

输入 N：4

1 3 0 2

时间：0.001秒

但是，当我输入 30 作为输入时，它需要异常长的时间，就好像它处于无限循环中一样。此外，当我输入 31 作为输入时，我花了将近 15 秒，但打印出来的时间只有 0.002 秒。我认为我应该更改时钟功能的位置，但由于代码在打印出第一个解决方案后退出程序，因此我决定将它们放在哪里变得非常棘手。

任何帮助将不胜感激。

我对 Golang 很陌生，我正在尝试用回溯算法做一个数独。但是当我运行我的程序时，没有错误，但它只显示网格不完整，这里有空的情况是我的代码：

我在控制台中得到这个：

我不明白为什么它没有完成网格，有人有什么想法吗？

我正在尝试编写字符串排列问题。而不是字符串，我有一个整数列表，如 [1,2,3]。我必须打印出列表的所有可能排列。但是，我的代码存在一些我无法弄清楚的问题。不知何故，if not in words基本案例中的行只命中一次。我试图从过去的一小时中弄清楚这一点。任何帮助，将不胜感激！。TIA 这是代码

我正在尝试解决这个算术表达式问题，我在数组中取 n（这里是 5）个元素并尝试 (+ - *) 中的所有运算符组合，以查找表达式是否可被 101 整除这里，我们不关心顺序操作员..不使用 BODMAS 输入

5

55 3 45 33 25

输出

55+3-45*33-25

我是递归和回溯的新手。我试图了解问题的哪一部分是错误的

这是我的代码：

在回溯之后，当我在 LINE2 进行更改并进入循环内部尝试下一个运算符时，更改工作正常，因为我在 LINE2 取回了原始号码，但它没有反映在 LINE1，这是我在尝试之前尝试恢复的最后一个号码LINE1 不反映运算符。

请帮助..任何帮助将不胜感激...

所以，我目前正在尝试解决这个问题，我有一个矩形场，我可以通过 6 种方式移动：

• 向上
• 正确的
• 对角线（右/上）
• 左（费用为 1）
• 羽绒服（费用为 1）
• 2 右 1 上，我称它为象棋中的马（成本 2）

如果达到或超过 10，成本将停止代码。

这是我的代码：

我确实认为它会找到一个解决方案，但它需要太多时间，即使对于小领域也是如此......我该如何改进我的代码？我应该采取另一种方法来解决这个问题吗？

我有清单：

我想检查它们是否形成这样的矩阵：

并将我的解决方案作为列表返回，例如：

我想出了这段代码：

我累了，不能再调试我的代码了。帮助将不胜感激。谢谢 ps：如果有更好的方法，我建议不要修复我的代码。

我正在尝试使用 Python 实现对遍历所有图形顶点的任意路径（不一定是循环）的递归搜索。这是我的代码：

这里，pt是起点，path是之前遍历的所有顶点的列表，不包括pt，默认为空。问题是，只要找到这样的路径，return 语句就会引用过程的某些内部调用，因此程序不会终止或返回路径。

例如，取G = {1:[2,3,4], 2:[1,3,4], 3:[1,2,4], 4:[1,2,3]}（即完整的 4-图）并运行hamilton(G,4,1,[]). 它返回None，但是如果您打印路径而不是将其作为值返回，您会看到它实际上找到了从 1 开始的所有六个路径。

如果我告诉程序将路径与 return 语句一起打印，它最终会打印所有这些路径，因此运行时间比需要的长得多。

如何修复代码，以便在找到第一个合适的路径后终止执行？

我正在解决有关LeetCode的以下问题：

编写一个接受整数 n 并返回其因子的所有可能组合的函数。例如，12应该返回：
[
   [2, 6],
   [2, 2, 3],
   [3, 4]
]

我想出了以下方法（在 C++ 中）：

这按预期工作，但在最后一个测试用例上超时：23848713.

一种被接受和赞成的解决方案（在 Java 中）如下：

两个代码的时间复杂度是相同的（在我看来）。那么为什么我的代码失败而其他代码成功运行23848713呢？我的意思是，我的代码中是否有一些明显的错误，还是在线法官有问题？

我感谢您的帮助。

编辑：<=n我for loop condition之前的代码中没有（只是因为其他代码有它 - 根据问题实际上并不需要它）。我后来把它包括在内。但无论如何，它仍然超时。

Edit2：在大 O 表示法中，我们跳过 的系数n。我认为这就是它在这里中断的原因。我的代码中这些常量的值很大。我想不出其他解释。

这个应该创建一个有效的数独字段。我已经删除了方格，这不是我现在遇到的问题的一部分，所以不要怀疑。

我的问题是，当无法正确添加 9 时，该方法会中断。我不知道如何让它回到前一点并计数，这将创建一个新的“路径”，所以我认为如果我做对了，一切都应该没问题。我仍在努力使用递归：-/

据我所知，我认为 sudokuCorrect() 做了它应该做的。编辑：您可以忽略布尔测试。我知道我不使用它，我试着想一些东西，但显然我不知道如何使用它。

输出是

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

| 2 | 1 | 4 | 3 | 6 | 5 | 8 | 7 | 9 |

分别当 squarechecker 被集成时，它看起来像

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

| 4 | 5 | 6 | 2 | 3 | 7 | 9 | 0 | 0 |

之后不管检查哪个变体。所以问题是一样的。

| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |