问题标签 [recursive-backtracking]

我正在开发一个函数，以递归方式生成给定数独难题的解决方案，该数独难题由 9x9 数组表示，NaN 表示利用回溯的空格。

返回的 cellSolutions 是一个元胞数组，其中包含 0、1 或更多解，具体取决于存在的解。我遇到的问题实际上是在初始调用返回的 cellSolution 中找到的解决方案。我希望的是：

我确实可以确认通过 disp 调用找到了一个或多个解决方案，但我不确定如何操作单元阵列。我很确定问题出在：

其他一些信息：reject 判断当前谜题是否满足数独规则；接受额外检查以确保没有空格；firstChild 在给定的数独谜题中找到 NaN 的实例，并将其更改为 1 并返回它更改的线性索引和新的谜题；nextChild 需要一个数独谜题和索引，如果该索引处的值不是 9，那么它会增加该值并返回新的谜题。谢谢！

For Java practice I started working on a method countBinary that accepts an integer n as a parameter that prints all binary numbers that have n digits in ascending order, printing each value on a separate line. Assuming n is non-negative and greater than 0, some example outputs would look like this.

I am getting pretty much nowhere with this. I am able to write a program that finds all possible letter combinations of a String and similar things, but I have been unable to make almost any progress with this specific problem using binary and integers.

Apparently the best way to go about this issue is by defining a helper method that accepts different parameters than the original method and by building up a set of characters as a String for eventual printing.

Important Note: I am NOT supposed to use for loops at all for this exercise.

Edit - Important Note: I need to have trailing 0's so that all outputs are the same length.

So far this is what I have:

When I run my code my output looks like this.

Can anyone explain to me why my method is not running the way I expect it to, and if possible show me a solution to my issue so that I might get the correct output? Thank you!

我正在为迷宫 [30][30] 编写查找路径解决方案，我在路径查找功能中使用了回溯；这是伪代码：

bool find_path(myMap,myVisited,myPath,v,h)

1. 找到起点然后为该点[v,h]运行函数find_path
2. 将房间标记为已访问
3. 终止条件1：如果h=29，在路径上标记然后返回true
4. 递归部分：搜索 8 个邻居：west,northwest,north,northeast,east,southeast,south,southwest。检查房间是否可访问，然后调用 find_path 函数，如果返回 true，则在查找路径上标记。
5. 终止条件2：返回false。

当我运行它时，它总是给出分段错误。我尝试了不同的方法，但都给出了相同的错误？输出应该是这样的图像： http ://postimg.org/image/cd8unwet5/ 这是我的代码：

我想按排序顺序仅通过单词“4”和“7”生成长度从 1 到 10 的所有字符串

我试过了，我的回溯代码看起来像这样

这是不正确的，请提出一个回溯算法来做同样的事情

注意：- 不用担心时间复杂性

我已经对以下程序进行了编码以递归地实现四色映射定理（简而言之，任何映射都只能用 4 种颜色着色，而没有任何相邻区域的颜色相同）。一切都可以编译，但我的输出给了我错误的数据（每个区域的颜色为-1，而不是现在的值 0-3）。我最大的问题是为什么输出不正确。

对于那些想知道的人，输入文件是一个邻接矩阵，如下所示：

这是我的代码：

只有一条规则要遵循：每个组的总和应该大于或等于它右侧的组。

我的猜测是构建一个包含所有分区选项的树，然后递归回溯。

例如，数组 14 13 2 11

结果：3. 3 个组（{14}、{13}、{2、11}）

你认为我的猜测是真的吗？如果没有，您还有其他解决问题的方法吗？

关于回溯解决方案的真正含义，我有几个问题。

1. 说，你有来自当前状态的 n 个选项，回溯解决方案基本上意味着你尝试所有这些状态，并对子问题做同样的事情（你可能有 n-1 个状态的解决方案），并且依此类推，然后返回从第 (n-1) 帧到第 n 帧的最佳解决方案。

请参阅下面的问题：给定长度为 n 的绳索，如何将绳索切成长度为 n[0]、n[1]、...、n[m-1] 的 m 个部分，以获得最大乘积of n[0] n[1] ... *n[m-1] Soa 长度的绳索将被切割成 2*3*3 得到 18 的乘积。,

2. 那么，所有回溯解决方案的时间复杂度都是指数级的吗？
3. 这听起来很像递归，我无法想象其他任何递归都能实现这样的效果。你能给我一个没有递归实现的回溯解决方案的例子吗
4. 它与蛮力有什么不同。这个问题的蛮力解决方案是尝试所有可能的方法组合来加起来n。我发现上述回溯解决方案的作用几乎相同。

使用 JAVA，我需要读取一个包含 n x n 表的文本文件，如下所示（尽管大小可能会有所不同）：

0110
1000
1001
0010

假设 n 是人数。该表描述了一个人（行）和另一个人（列）之间的关系。如果表值为1，则两者是朋友；如果为 0，则他们不是朋友。例如，(0,1) 为 1；因此，1 和 2 是朋友。我需要从给定数量的字母（在此特定表的情况下：2）中为表中的每个人分配一个字母。如果两个人是朋友，他们必须收到不同的信。人们不被视为自己的朋友。使用递归回溯我需要找到这个难题的解决方案并将其打印出来或确定没有解决方案是可能的。

编辑：除非在表格中明确说明，否则朋友的朋友不被视为朋友。例如，在这个表中，1 是 2 和 3 的朋友；但是 2 和 3 不是朋友。1和3是朋友，3和4是朋友，但1和4不是朋友。我还应该注意，我在这里的编号是自然的，而实际上表索引从 0 开始。

我不知道从哪里开始解决这个问题。我确实意识到桌子有一条从 (0,0) 到 (n,n) 的对称线，因为如果 (1,2) 是朋友 (2,1) 也是朋友，因此没有人是他们自己的朋友（ n,n) 将始终为 0。

编辑：为了直观地显示它，在我看来，解决问题只需要粗体信息。

0 110
10 00
100 1
0010

总是将字母 A 分配给第 1 个人似乎是合理的，然后查看行并将不同的字母分配给值为 1 的位置。我不确定如何准确地执行此操作，也没有必要分配 2 和 3 不同此时的字母（回溯将在稍后处理）。

编辑：我可以使用以下内容为一个人分配一个随机数（稍后将转换为一个字母）。然后可以将该号码添加到排除列表中，该列表将排除这些号码分配给具有值 1 的行中的人（朋友）。

编辑：

到目前为止我有这个代码；但是，我似乎无法找到如何使用回溯来做到这一点。另外，我不确定这是否适用于更大的桌子。在我看来，我需要修改我的排除实现。

你有什么建议可以帮助我走上正确的道路吗？

谢谢！

所以最近看到英国GCHQ发的这个谜题：

它涉及求解 25x25 非图：

非图是图片逻辑谜题，其中网格中的单元格必须根据网格一侧的数字着色或留空，以显示隐藏的图片。在这种拼图类型中，数字是离散断层扫描的一种形式，用于测量任何给定的行或列中有多少完整的实心正方形线。例如，“4 8 3”的线索意味着有四个、八个和三个实心方块按顺序排列，连续组之间至少有一个空白方块。

自然地，我倾向于尝试编写一个可以为我解决问题的程序。我正在考虑从第 0 行开始的递归回溯算法，并且对于给定行线索中的信息的该行的每个可能排列，它放置下一行的可能组合并验证它是否是给定列的有效位置线索。如果是，则继续，如果不是，则回溯，直到所有行都置于有效配置中，或者所有可能的行组合都已用尽。

我在几个 5x5 拼图上对其进行了测试，效果很好。问题是计算 25x25 GCHQ 拼图需要很长时间。我需要让这个算法更高效的方法——足以解决上面链接的难题。有任何想法吗？

这是我为每一行生成一组行可能性的代码以及求解器的代码（注意*它使用了一些非标准库，但这不应该偏离重点）：

好吧，我有这张图：

我必须制作一个基于 Branch and Bound 并使用回溯的代码，它必须显示匹配图形节点的最佳方式。所以在这个例子中，最优解必须是>> [(1,4),(2,3)]。但是我的算法显示了这个可能的解决方案，这不是最佳的>> [(1,2),(3,4)]。我认为问题可能出在“撤消”行，但我不确定......如果有人可以帮助我解决这个问题，我将非常感激！

这是我的代码：