java - 解决难题的编程设计

Question

抱歉，如果我在这里发布错误。但我有点不知道应该在哪个 Stackoverflow channel 发布此内容，并认为这是最好的。

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

为了解决这个难题，我将有一个输入，我可以在其中获取每个笼子的值，例如笼子的总值(value)，所涉及的广告框所使用的运算符(operator)。

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

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

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

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

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

Answer 1

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

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

对于回溯，通常使用堆栈。因此，您可能有一堆物体，这些物体会告诉您将哪个数字放入哪个笼子中。 现在，您可以为每个堆栈对象提供一个属性，该属性告诉您的算法是否只是从一堆可能性中选择了这个数字，或者您的算法是否被迫在这个地方选择了这个数字，因为它没有其他选择。 因此，不要使用这样的堆栈:

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

你的堆栈看起来像这样:

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

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