0

对不起，如果我在这里发错了。但我有点不知道我应该在哪个 Stackoverflow 频道发布这个，并认为这是最好的。

我正在解决一个 KenKen 拼图。它与数独非常相似，并且有一些带有总和和运算符的笼子，我们必须使用唯一的数字来解决填充框。

为了解决这个难题，我将有一个输入，我可以在其中获取每个笼子的值，例如笼子的总价值，要使用的广告盒的运营商。

根据我使用回溯解决问题的方法：

  1. 我正在解析输入以为每个笼子创建一个类数据结构。

  2. 后来我为每个笼子创建了一个类对象数组。

  3. 此后，我将使用回溯应用我的算法来解决这个难题。

在我开始编码之前，我只是想在这里与人们讨论一下，如果他们确实认为编程方法是正确的，或者我是否仍然需要对方法进行更改，或者他们是否想建议我解决一些问题。

4

1 回答 1

1

我认为回溯可能是解决这个问题的最好方法之一。老实说，我现在想不出更好的东西。

我不知道你到底打算在你的算法中做什么。但我建议你不应该只依赖回溯本身。我只看了维基百科上的文章才知道 KenKen 是什么。但似乎有可能从一开始就改进回溯：

对于回溯，您通常使用堆栈。因此，您可能有一叠物品，这些物品会告诉您将哪个数字放在哪个笼子里。现在你可以给每个堆栈对象一个属性，告诉你的算法是否只是从一堆可能性中选择了这个数字，或者你的算法是否因为没有其他选择而被迫在这个地方选择这个数字。所以代替这样的堆栈：

(2,2) 5
(1,1) 4
(0,0) 1

您的堆栈将如下所示：

(2,2) 5 CHOSEN
(1,1) 4 IMPLIED
(0,0) 1 CHOSEN

然后你必须只回溯到最后一个“暗示”，因为你不能在这里选择其他值。此外，如果所有其他选择都被证明是错误的，则会暗示一些事情。我不知道这在 KenKen 中能走多远。你应该确保，一开始的选择不能强迫你的算法稍后使用 IMPLIED，尽管这个数字实际上不是 IMPLIED 的。

于 2012-09-21T06:45:56.083 回答