问题标签 [recursive-backtracking]

这是我的主要递归函数，它似乎根本不起作用，并且具有比我预期的更奇怪的行为。我究竟做错了什么？PS 下面的函数是类的一部分。如果需要，将包括其余代码..

Below is the code I am using to test backtracking algo to solve knight's tour, and it's not able to solve for odd board sizes. I would really appreciate if someone could point out the error in the code.

The code works fine for boards of even size, but it fails to find a solution for boards of odd sizes.

关于如何将递归转换为非递归有很多问题，我也可以将一些递归程序转换为非递归形式注意：我使用一种通用的方式（用户定义的堆栈），因为我认为它很容易理解，并且我使用 Java，所以不能使用 GOTO 关键字。

事情并不总是那么顺利，当我遇到回溯时，我被卡住了。例如，子集问题。我的代码在这里：recursive call with loop

当我使用用户定义的堆栈将其转换为非递归形式时。我不知道如何处理循环（在循环中存在递归调用）。

我google了一下发现有很多方法，比如CPS。我知道有一个子集问题的迭代模板。但我只想使用用户定义的堆栈来解决。

有人可以提供一些线索来将这种递归（循环递归）转换为非递归形式（通过使用用户定义的堆栈，而不是 CPS 等）吗？

这是我的代码递归到非递归（Inorder-Traversal），因为递归调用没有循环，所以我可以轻松做到。同样，当具有返回值的递归程序时，我可以使用引用并将其作为参数传递给函数。从代码中，我使用堆栈来模拟递归调用，并使用“状态”变量到下一个调用点（因为 java 不允许使用 GOTO）。

以下是我收集到的信息。似乎所有这些都不满足我提到的问题（有些使用 goto 不允许 java，有些是非常简单的递归意味着没有嵌套递归调用或带有循环的递归调用）。

1旧自治领大学

2代码项目

----------------------------------分割线-------------- ----------------------

谢谢你们。在我发布问题之后......我花了一整夜才弄清楚。这是我的解决方案：非递归子集问题解决方案，代码的注释是我的想法。

总结一下。我之前坚持的是如何处理 foo-loop，实际上，我们可以简单地忽略它。因为我们使用的是loop+stack，所以可以对是否满足条件做一个简单的判断。

经典的 N-Queens 问题找到了一种将 n 个皇后放置在 n×n 棋盘上的方法，这样两个皇后就不会相互攻击。这是我对 N-Queens 问题的解决方案。

这个问题的扩展状态，找到所有可能的解决方案并以列表的形式返回它们。我尝试通过将列变量添加到辅助方法来扩展我的解决方案，该方法从 0 开始以跟踪一个完整的解决方案和下一个解决方案的开始。因此基本情况变为

但是这种方法不起作用，因为每个连续的递归调用都会在错误的列中结束。有人可以帮助扩展此解决方案以找到所有可能的解决方案。

我花了很多时间思考一种方法来实现基于回溯的数独求解算法。但是，我遇到了一个问题——算法一旦出错就不会回溯。为了使事情尽可能简单，这是我的主要功能：

数独类的构造函数创建一个空棋盘，然后计算机必须用满足数独规则的数字填充整个网格。
FindEmptyCell 方法将字段行和列的值设置为等于第一个未占用单元格的索引。这个网格代表我的程序返回 false 时的状态：

请你告诉我，到目前为止，我的算法是否一切都正确？如果是这样，那就意味着错误出在辅助功能的某个地方。例如，我不知道使用字段来存储索引是否不会阻止回溯。
任何帮助，将不胜感激。另外，如果这篇文章在某种程度上违反了这个委员会的规则，请在投票前在评论中告诉我——我希望以后避免这些错误。

编辑：提供剩余的方法：

我在搜索回溯时遇到了一些问题。首先，在下面链接的代码中，作为一名 JavaScript 程序员，我发现了一个非常奇怪的语法：

使用此页面中的信息，我发现它的意思是：“分配a[i]给a[l]变量和a[l]变量a[i]”。我无法理解这个的用途。我认为这将是相同的值。如果您首先将值分配给a[l]，然后尝试获取a[l]，那么这两个变量都将是a[i], 。

这是一个 Python 代码，但是，我想使用相同的原理将其转换为 JavaScript。

您可以通过此链接访问 IDE：https ://ide.geeksforgeeks.org/ASvO8MoGQr 。

这段代码的作用是获取字符串“aab”的排列值。

例如，使用“aab”作为第一个字符串，我们应该得到以下结果：aab aba aab aba baa baa。

我尝试使用“JavaScript”并想出了这个：

我得到的结果是["aab", "aab", "aab", "aab", "aab", "aab"].

链接到 JSFiddle：https ://jsfiddle.net/xrfkt9qj/1/ 。

EDIT1我尝试了@jp_data_analysis 的答案，但它仍然返回不好的结果：https ://jsfiddle.net/zurvm0xy/ 。

EDIT2 ES6 版本的脚本：https://jsfiddle.net/zurvm0xy/4/。

它不是重复的，变量交换只是这个问题的第一部分。请阅读全文。

因此，查看有关使用递归解决迷宫的所有其他论坛，他们都没有帮助我解决我的问题。

我从输入文件中得到一个迷宫，并且有一个开始和结束位置。我发现 start pos 通过引用传递了 x 和 y 并递归地解决了迷宫。我的问题是迷宫中每个可能的位置都充满了标志。当只标记解决方案路径时（'@'是我们用来显示解决方案路径的东西）

这是我编译和运行时我的代码输出的内容：

如您所见，“N”是函数发现死胡同并需要回溯和擦除它们的地方。'@' 符号是正确的路径，它只是在回溯时不会擦除

我相信我的问题是 find_exit 函数或 at_end 函数

这是代码：

sample_input.txt 文件如下：

这些是我们应该解决的迷宫。

我也不允许编辑头文件。

这就是输出的样子：

所以我尝试通过回溯算法来实现数独。我不明白为什么我的代码没有给出预期的输出。

我所做的是，我创建了一个循环，它在其中检查数独中的空单元格（用 0 表示）。当它找到它时，它的坐标被传递给一个名为 possibleEntriescheck() 的函数。此函数写入一个名为 possibleEntries[9] 的全局声明数组，这些数字可能填充到最初传递坐标的单元格中。

我从这些视频中学到了这个算法： https://www.youtube.com/watch ?v=NuodN41aK3g https://www.youtube.com/watch?v=QI0diwmx3OY

预期的输出是一个已解决的数独。它没有按预期执行。相反，它冻结了。一点帮助就意味着很多。谢谢你。

我在回溯时遇到了一些困难。

1. 如何定义用于回溯问题的全局列表？我看到了几个答案，他们都建议在变量名前面使用'global'关键字，在函数内部用作全局。但是，它在这里给了我一个错误。

2. 有没有什么好的通用方法可以用来获取结果，而不是全局变量？

下面的代码试图解决回溯问题，其中给出了一个数字列表，我们必须找到添加到目标的唯一数字对（不允许排列）。

有人可以给我答案/建议吗？

我一直试图找出发生此错误的原因，但一无所获。这是来自回溯的 n-queen 问题的代码。但这没关系。我想知道为什么会发生这个错误以及如何解决它。

new.C:5:32: 错误: 使用未声明的标识符's' bool attack_checking(int arr[][s], int s, int i, int j) { ^

new.C:32:22：错误：使用未声明的标识符“s”

布尔皇后（int arr[][s]，int l）{ ^

产生 2 个错误。