logo标签列表

解决Kakuro难题

calgorithm
9

下面是一个值得思考的题目：

http://zh.wikipedia.org/wiki/数独

我正在尝试制作这个游戏的求解器。已经完成了前期工作（读取一个包含可变数量列和行的初始文件）。假设输入文件遵循游戏规则，因此游戏始终是可以解决的。请花时间阅读游戏规则。

我已经处理好了最适合的数据结构：

struct aSquare { int verticalSum; int horizontalSum; int value; }

我创建了一个“数组”来动态处理这些内容。我将黑色方块的值设为-1，白色方块（实际解决方案方块）初始化为0。您还可以轻松地从数组中获取每个aSquare结构的位置，无需为其创建额外的结构字段。
现在是算法...我该如何协调所有这些总和，并找到一种通用的方法来解决所有类型的网格。我整个下午都在苦苦挣扎，但没有结果。
欢迎提供帮助，祝愉快！
*编辑：我刚刚意识到我发布的实际链接有一些关于解决技巧的提示。尽管如此，我仍将保留此链接，以查看人们想出什么。
6个回答
9

关于约束编程：以下是使用约束编程解决Kakuro难题的不同实现方式（均使用相同的基本原则）。问题实例在程序中已经固定。

编辑：添加了Google or-tools/C#和Answer Set Programming。

5

一个简单的数独暴力求解器只需要几毫秒就能运行，因此您无需实现任何特殊策略。我认为在Kakuro的情况下也是如此。一个简单的算法：

def solve(kakuro):
    if kakuro has no empty fields:
        print kakuro
        stop.
    else:
        position = pick a position
        values = [calculate possible legal values for that field]
        for value in values:
            kakuro[position] = value
            solve(kakuro)
        kakuro[position] = None # unset after trying all possibilities

如果您能找到最佳的填充字段顺序，这个算法可能会更好地工作。尝试选择那些受限制最多的字段（即：合法值不多）。

无论如何，这可能是最简单的实现方式，因此请先尝试它，并仅在此方法无效时寻找更复杂的求解器。（实际上，这是最简单的约束编程求解器之一；当然，真正的CP求解器要复杂得多。）

请注意，在“[计算该字段可能的合法值]”步骤中有很多巧妙的空间。 - Brian
@Brian：更多是为了选择一个位置，因为在许多算法中，这可能意味着从多项式时间到指数时间的转换。Kakoru是NP完全问题，但明智地选择顺序可能会使常数小得多。而且，使用适当的数据结构计算可能的合法值应该是常数时间。 - liori
好的。在我设计的解算器中（用于另一个谜题），我使用的一个技巧是选择每个位置并尝试进行一次迭代，使用反证法来减少可能合法值的数量。我还填充了只有一个可能合法值的所有空格。因此，我的谜题实际上具有[计算每个字段的可能合法值]函数。我的位置选择器用于猜测没有任何智能，实际上也不需要。公平地说，Nurikabe是一个二进制谜题，因此所有位置都同样受到限制。 - Brian
2
如果您的兴趣最终在于为这些游戏制作软件求解器，但不涉及算法细节，我建议使用约束编程（CP）引擎。CP是一种声明式编程范例，非常适合这些问题。有几个商业和开源的CP引擎可供选择。 http://en.wikipedia.org/wiki/Constraint_programming
目前实际上只是这个游戏。我本来想为自己制作更复杂的东西。不过还是谢谢你的建议。 - Qosmo
1
0
这是直接的线性代数问题，使用向量/矩阵操作技巧来解决。
[编辑 - 回答评论]
a + b + 0 + d + 0  = n1
0 + b + c + 0 + e  = n2
a + 0 + c + 0 + 0  = n3
a + b + c + 0 + e  = n4
a + 0 + c + d + 0  = n5

以上被转换为矩阵，通过添加和减去行的倍数，最终得到：
a 0 0 0 0 na
0 b 0 0 0 nb
0 0 c 0 0 nc
0 0 0 d 0 nd
0 0 0 0 e ne

没有组合数学，所有的数字都保持整数。

1
使用线性代数通常不会得到整数解。组合数学需要以某种方式进入。 - Philip Starhill
3
线性代数无法表示不重复数字的规则。 - liori
在你的例子中，有一个消元顺序，其中解是所有整数，但对于一般的0-1矩阵找到这样的顺序并不容易。尝试按照你提出的顺序进行高斯消元，你会发现1/2悄悄地出现了。在这种情况下，一个好的顺序很容易找到（一个例子是a，b，d，c，e），但通常情况下，你需要能够在GE中回溯，以防后来的矩阵元素由于早期决策而变成分数。 - Philip Starhill
记住了这个技巧，觉得它可能会有所帮助。（其实忘了这是高斯的 - 谢谢） - slashmais
再仔细思考一下，我意识到我的观点关于1/2的问题并不是全部。如果您有一个正方形可逆矩阵，即使在高斯消元中出现分数，您也会得到正确的答案。真正的问题是Kakuro谜题的系统是欠定的（在维基百科的例子中，您会得到一个24x36的矩阵），因此一旦完成，您必须想办法分配所有自由变量以使其余部分成为整数。这将大大缩小搜索空间，因此它可以作为回溯方法中的预处理步骤来帮助解决问题。 - Philip Starhill
0

我发现了一些不错的位运算技巧，可以加速Kakuro的解决。你可以在这里获取源代码here。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接