问题标签 [recursive-backtracking]

我正在根据这个算法使用回溯实现填字游戏生成器：这是我的伪代码：

这是我当前的代码（C#）：

我的问题是，对于网格 NxN，例如 6X6，我发现对于大于 N 的字数，我的算法找不到解决方案 - 10 秒或更长时间后；/，对于小于或等于 N 的字数，它可以正常工作，提前感谢任何帮助！

我正在尝试解决一个难题，我将其分解为两个都需要递归的独立问题。当第一个递归问题得到解决时，我想调用下一个递归问题，当它解决时，难题就完成了。我的问题是，当第一个递归问题提出解决其问题的解决方案但它不是解决难题的正确解决方案时，第二个递归案例失败了。

例如，如果您有一个谜题 C，它分为 2 部分 A 和 B。然后您将使用 A 的解决方案来解决 B，解决 B 将解决 C。

我的问题是如何设置递归（递归调用将在哪里进行，所以如果第二部分失败，它将为第一部分找到新的解决方案）？

我正在解决大约 2 年前在我的课程中给出的一个测试，它得到了以下方法

现在，我在我的 IDE 上运行它，发现它打印了所有可能的 k 单元格和 n 个数字的组合。我也花时间用调试器来跟踪它，但我就是不明白它背后的逻辑是什么

我的意思是，作为开发人员，我该如何创建这样的递归。这个回溯背后的逻辑是什么

我使用正则表达式来验证数字格式。

当我为某些输入处理大量输入时，它似乎无限循环。我阅读了有关灾难性回溯的其他答案。但我是一个正则表达式新手，需要一些帮助。您能否提供任何可以使这个正则表达式灾难性地回溯的输入。对我理解会有帮助。谢谢。这也可能是一个很长的输入。我正在使用 Java 模式和匹配器对象。

该程序正在使用回溯来找出迷宫的出路（它做得很好）。当我尝试打印出我选择的正确路径时，就会出现问题。这是我的solveMaze() 方法。

当我回溯时，我正在拾取我的标记，但它似乎也在正确的路径上拾取标记，并打印出一个带有破碎路径的迷宫。

我正在尝试编写一个程序，该程序将使用回溯来创建数独求解器。我已经能够创建一个黑色数独网格，我可以检查一个动作是否是有效的动作。我的程序运行良好，直到一个正方形有多个数字可供选择。

问题：你会看看我的 Solve 方法，看看我如何修改它以回溯，更改答案并再次前进。我给出了上面所有其他方法的名称以及每一种方法的名称。

示例输入：

电流输出示例：

我的程序在第一行的最后 0 处停止，因为没有解决方案，除非前 4 更改为 7，否则程序终止。

我想用一组变量（例如1到10）在R中创建一个矩阵。这些变量应该在行和列上随机分配，但不应该在任何一个中重复（所以数字 1 应该在第 1 行中一次，在第 1 列中一次）！

例如：

1,2,3,4,5,6,7,8,9,10

2,3,4,5,6,7,8,9,10,1

3,4,5,6,7,8,9,10,1,2

4,5,6,7,8,9,10,1,2,3

5,6,7,8,9,10,1,2,3,4

6,7,8,9,10,1,2,3,4,5

7,8,9,10,1,2,3,4,5,6

8,9,10,1,2,3,4,5,6,7

9,10,1,2,3,4,5,6,7,8

10,1,2,3,4,5,6,7,8,9

但当然，在那个例子中，数字是递增的，我希望它们随机化。我尝试了简单的矩阵要求，但我无法弄清楚如何做到这一点。任何人都可以帮忙吗？提前致谢！

我有这个独特的要求，即找到 2 年前的文件并删除它们。但不仅是文件，还有相应的空目录。我已经编写了大部分逻辑，但唯一仍然悬而未决的是，当我从目录中删除特定文件时，如何在相应目录为空时删除相应目录。当我删除特定文件时，ctime/mtime 也会相应地得到更新。如何定位那些相应的旧目录并删除它们？任何指针都会有所帮助。提前致谢。

• 行政

这是我们需要实现的功能。seq 和 item 来自这些测试函数。

我们在顶部有多个起点。我们得到了 car(lst) 函数：

我们还得到了 cdr(lst) 函数：

最后，我们得到了 cons 函数：

我试图修复实现代码，但是，由于某种原因，我尝试的代码返回此错误：

这是我的代码：

你们能告诉我我做错了什么吗？或者如何解决？太感谢了！！！

假设有一个 1 和 0 的 2D 网格，例如 -

网格被“折叠”以形成一个少 1 行和 1 列的较小网格，因此上述示例将“折叠”以形成 3 行和 3 列的网格。

新值由以下规则确定 -

所以对于示例网格， out of [0][0], [0][1], [1][0] and [1][1], only [0][1]is 1，所以[0][0]在新网格中将为 1。类似地， out of [0][1], [0][2], [1][1] and [1][2], both [0][1] and [1][2]are 1，所以[0][1]innew_grid将为 0。

输入以值的形式给出new_grid。我必须找出可能的配置数量old_grid，这new_grid可以通过提供的折叠规则来实现。

我的方法

我目前想到的回溯解决方案是这样的——

1. 为旧网格中的每个 1 值单元格识别假想的 2X2 框，这将对应于新网格中的适当单元格。

2. 所有这些盒子都将包含一个值为 1 的单元格，因此将 1 放入每个盒子的随机单元格中。

3. 递归检查在随机单元格中放置 1 是否确保每个框仍然恰好保留一个值为 1 的单元格。

4. 如果最终获得了一个网格配置，其中每个框恰好包含一个值为 1 的单元格，请检查该配置是否可以“折叠”以获取新网格。

5. 如果不是，则使用值为 1 的不同单元格重复该过程。

如果旧网格中有一些不属于任何“框”的单元格，那么它们就是我所说的“无关紧要”单元格。

例如 -

对于上述new_grid情况，old_grid可以是 -

或者

最后一行的单元格是“无关紧要”的单元格，因为它们不属于任何 2X2 框，并且它们都可以是1s 或0s 是有效的配置（我认为这是我们可以灵活操作它们的程度，虽然我不确定）。

我的问题是——这个算法很可能是指数级增长的，说50X10.

有没有其他方法可以解决这个问题？或者是否有任何聪明的算法不通过所有可能的配置来计算它们？